Mathematical Induction

Base Case

For $n=1$,

So the statement is true for $n=1$.

Inductive Hypothesis

Assume that for some positive integer $k$,

Inductive Step

Then

This is exactly the required formula for $n=k+1$.

Therefore, by induction,

for every positive integer $n$.

Base Case

For $n=0$,

Inductive Hypothesis

Assume

Inductive Step

Then

Since

for $k\ge0$,

Therefore,

for all $n\ge0$.

Base Case

Inductive Hypothesis

Assume

Then

Thus the formula holds for $k+1$.

Therefore,

We prove the identity by induction on $n$.

Base Case

For $n=0$,

The right-hand side is

So the identity holds for $n=0$.

Inductive Hypothesis

Assume that the identity holds for $n=k$:

Inductive Step

For $n=k+1$, add the next term:

This is exactly the required formula for $n=k+1$.

Therefore, by induction,

for all nonnegative integers $m,n$.

We prove the statement by induction on $n$.

Base Case

For $n=0$,

which is divisible by

So the statement holds for $n=0$.

Inductive Hypothesis

Assume that for some nonnegative integer $k$,

Thus, for some integer $m$,

Inductive Step

We need to prove

Let

Then

Factor:

By the inductive hypothesis,

Also, since $3^k$ is odd,

Therefore,

Hence

So one factor is divisible by $3^{k+1}$ and the other is divisible by $3$. Therefore,

Thus,

Therefore, by induction,

for every nonnegative integer $n$.

We prove the inequality by induction on $n$.

Base Case

For $n=1$,

which is true.

Inductive Hypothesis

Assume that for some positive integer $k$,

Inductive Step

For $n=k+1$,

It remains to show that

Equivalently,

Since both sides are positive, we may square:

But

Therefore,

Hence, by induction,

for every positive integer $n$.

Base Case

For $n=1$, the board is

Inductive Hypothesis

Assume that any

board with one cell removed can be tiled with L-shaped trominoes.

Inductive Step

Consider a

board with one cell removed.

Divide the board into four

quadrants.

The missing cell lies in one of these four quadrants.

Place one L-shaped tromino at the center of the board so that it covers one central cell from each of the other three quadrants.

Now each quadrant has exactly one missing cell:

• The quadrant containing the original missing cell already has one missing cell.
• Each of the other three quadrants has one cell covered by the central tromino.

Thus each quadrant is a

board with one cell missing.

By the inductive hypothesis, each of the four quadrants can be tiled with L-shaped trominoes.

Together with the central tromino, this tiles the entire board except for the originally removed cell.

Therefore, by induction, any

board with one cell removed can be tiled with L-shaped trominoes for every positive integer $n$.

Let $f(m)$ denote the largest odd factor of the positive integer $m$.

We prove by induction that

Base Case

For $n=1$, the only integer is $2$, whose largest odd factor is $1$. Hence

So the statement holds for $n=1$.

Inductive Hypothesis

Assume that for some positive integer $k$,

Inductive Step

For $n=k+1$, we need the largest odd factors of

Compared with the previous sum, we remove $f(k+1)$ and add

Since $2k+1$ is odd,

Also, multiplying a number by $2$ does not change its largest odd factor, so

Therefore,

Thus the statement holds for $k+1$.

Therefore, by induction,

for every positive integer $n$.

Assume that

is an integer. Prove that for every positive integer $n$,

is also an integer.

Prove that for every integer $n\ge6$, a square can be divided into exactly $n$ smaller squares.

Prove that for every positive integer $n$, there exists a permutation of

such that for any two elements $a$ and $b$, their arithmetic mean

is not an element appearing between $a$ and $b$ in the permutation.

For example,

does not satisfy the condition, since $5$ appears between $3$ and $7$, and

On the other hand,

satisfies the condition.