Mathematical Induction: Problems with Solutions

Solution:
Since [tex]1+2+\ldots+n=\frac{n(n+1)}{2}[/tex] (sum of an arithmetic progression), it suffices to prove that
[tex]S_{n}=1^{3}+2^{3}+\ldots+n^{3}=\frac{n^{2}(n+1)^{2}}{4}[/tex]
We use mathematical induction on [tex]n[/tex]. Base case: for [tex]n=1[/tex] we have [tex]S_{1}=1=\frac{1^{2}\times 2^{2}}{4}[/tex].
Inductive step: assume that [tex]S_{k}=\frac{k^{2}(k+1)^{2}}{4}[/tex] for some natural number [tex]k[/tex]. Then
[tex]S_{k+1}=S_{k}+(k+1)^{3}=\frac{k^{2}(k+1)^{2}}{4}+(k+1)^{3}=\frac{(k+1)^{2}\left(k^{2}+4k+4\right)}{4}=\frac{(k+1)^{2}(k+2)^{2}}{4}[/tex]
which is the formula for [tex]n=k+1[/tex]. By the principle of mathematical induction, for every natural [tex]n[/tex]
[tex]1^{3}+2^{3}+\ldots+n^{3}=\left(\frac{n(n+1)}{2}\right)^{2}=\left(1+2+\ldots+n\right)^{2}[/tex]

Solution:
Fix [tex]x\ge -1[/tex] and use induction on [tex]n[/tex]. Base case: for [tex]n=1[/tex] the inequality becomes [tex]1+x\ge 1+x[/tex], which is true (equality).
Inductive step: assume that [tex]\left(1+x\right)^{k}\ge 1+kx[/tex] for some natural number [tex]k[/tex]. Since [tex]x\ge -1[/tex], we have [tex]1+x\ge 0[/tex], so multiplying both sides by [tex]1+x[/tex] keeps the direction of the inequality:
[tex]\left(1+x\right)^{k+1}\ge (1+kx)(1+x)=1+(k+1)x+kx^{2}\ge 1+(k+1)x[/tex]
because [tex]kx^{2}\ge 0[/tex]. This is the inequality for [tex]n=k+1[/tex], so by induction it holds for every natural [tex]n[/tex]. The condition [tex]x\ge -1[/tex] is exactly what allows the multiplication by [tex]1+x[/tex].

Solution:
Let [tex]A_{n}=4^{n}+15n-1[/tex]. We use induction on [tex]n[/tex]. Base case: [tex]A_{1}=4+15-1=18=9\times 2[/tex] is divisible by [tex]9[/tex].
Inductive step: assume that [tex]A_{k}[/tex] is divisible by [tex]9[/tex] for some natural number [tex]k[/tex]. We express [tex]A_{k+1}[/tex] through [tex]A_{k}[/tex]:
[tex]A_{k+1}=4\times 4^{k}+15k+14=4\left(4^{k}+15k-1\right)-45k+18=4A_{k}-9(5k-2)[/tex]
The number [tex]4A_{k}[/tex] is divisible by [tex]9[/tex] by the induction hypothesis and [tex]9(5k-2)[/tex] is a multiple of [tex]9[/tex], so [tex]A_{k+1}[/tex] is divisible by [tex]9[/tex]. By induction, [tex]4^{n}+15n-1[/tex] is divisible by [tex]9[/tex] for every natural [tex]n[/tex].

Solution:
We compute the first values:
[tex]P_{2}=\frac{3}{4}, \quad P_{3}=\frac{3}{4}\times \frac{8}{9}=\frac{2}{3}=\frac{4}{6}, \quad P_{4}=\frac{2}{3}\times \frac{15}{16}=\frac{5}{8}[/tex]
The values [tex]\frac{3}{4}[/tex], [tex]\frac{4}{6}[/tex], [tex]\frac{5}{8}[/tex] suggest that [tex]P_{n}=\frac{n+1}{2n}[/tex]. We prove it by induction for [tex]n\ge 2[/tex]. Base case: [tex]P_{2}=\frac{3}{4}=\frac{2+1}{2\times 2}[/tex].
Inductive step: assume that [tex]P_{k}=\frac{k+1}{2k}[/tex] for some [tex]k\ge 2[/tex]. Then
[tex]P_{k+1}=P_{k}\left(1-\frac{1}{(k+1)^{2}}\right)=\frac{k+1}{2k}\times \frac{k(k+2)}{(k+1)^{2}}=\frac{k+2}{2(k+1)}[/tex]
which is the formula for [tex]n=k+1[/tex]. Hence [tex]P_{n}=\frac{n+1}{2n}[/tex] for every [tex]n\ge 2[/tex].
The formulas [tex]\frac{n+1}{n+2}[/tex] and [tex]\frac{n^{2}-1}{n^{2}}[/tex] give the correct value [tex]P_{2}=\frac{3}{4}[/tex] but fail already for [tex]n=3[/tex], and [tex]\frac{n+2}{2(n+1)}[/tex] is shifted by one index (it equals [tex]P_{n+1}[/tex]).

Solution:
Each term is determined by the two previous ones, so we check two base cases and assume the formula for two consecutive indices. Base case: for [tex]n=1[/tex] and [tex]n=2[/tex]:
[tex]3\times 2^{0}+2\times (-1)^{1}=1=a_{1}, \quad 3\times 2^{1}+2\times (-1)^{2}=8=a_{2}[/tex]
Inductive step: assume that for some [tex]k\ge 3[/tex] the formula holds for [tex]n=k-2[/tex] and [tex]n=k-1[/tex]. Using [tex](-1)^{k-1}=-(-1)^{k}[/tex] and [tex](-1)^{k-2}=(-1)^{k}[/tex], we get
[tex]a_{k}=a_{k-1}+2a_{k-2}=3\times 2^{k-2}+2(-1)^{k-1}+2\left(3\times 2^{k-3}+2(-1)^{k-2}\right)[/tex]
[tex]=3\times 2^{k-2}+3\times 2^{k-2}+(-1)^{k}(-2+4)=3\times 2^{k-1}+2\times (-1)^{k}[/tex]
So the formula holds for [tex]n=k[/tex], and by (strong) induction it holds for every natural [tex]n[/tex].

Solution:
Let [tex]S_{n}[/tex] be the left side; it consists of the [tex]2n+1[/tex] terms from [tex]\frac{1}{n+1}[/tex] to [tex]\frac{1}{3n+1}[/tex]. We use induction on [tex]n[/tex]. Base case:
[tex]S_{1}=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{13}{12}\gt 1[/tex]
Inductive step: assume that [tex]S_{k}\gt 1[/tex] for some natural number [tex]k[/tex]. Compared with [tex]S_{k}[/tex], the sum [tex]S_{k+1}=\frac{1}{k+2}+\ldots+\frac{1}{3k+4}[/tex] loses the term [tex]\frac{1}{k+1}[/tex] and gains the three terms [tex]\frac{1}{3k+2}[/tex], [tex]\frac{1}{3k+3}[/tex], [tex]\frac{1}{3k+4}[/tex]:
[tex]S_{k+1}=S_{k}+\frac{1}{3k+2}+\frac{1}{3k+3}+\frac{1}{3k+4}-\frac{1}{k+1}[/tex]
Since [tex]\frac{1}{k+1}=\frac{3}{3k+3}[/tex], with [tex]m=3k+3[/tex] we get
[tex]S_{k+1}-S_{k}=\frac{1}{m-1}+\frac{1}{m+1}-\frac{2}{m}=\frac{2m}{m^{2}-1}-\frac{2}{m}=\frac{2}{m\left(m^{2}-1\right)}\gt 0[/tex]
because [tex]m\ge 6[/tex]. Therefore [tex]S_{k+1}\gt S_{k}\gt 1[/tex], and by induction the inequality holds for every natural [tex]n[/tex].

Solution:
We use induction on [tex]n[/tex] (for all [tex]x[/tex] at once). Base case: for [tex]n=1[/tex] the inequality is [tex]\left|\sin x\right|\le\left|\sin x\right|[/tex], which is true.
Inductive step: assume that [tex]\left|\sin kx\right|\le k\left|\sin x\right|[/tex] for some natural number [tex]k[/tex] and every real [tex]x[/tex]. By the addition formula
[tex]\sin (k+1)x=\sin kx\cos x+\cos kx\sin x[/tex]
Using the triangle inequality, the bounds [tex]\left|\cos x\right|\le 1[/tex], [tex]\left|\cos kx\right|\le 1[/tex] and the induction hypothesis, we get
[tex]\left|\sin (k+1)x\right|\le\left|\sin kx\right|\left|\cos x\right|+\left|\cos kx\right|\left|\sin x\right|\le\left|\sin kx\right|+\left|\sin x\right|[/tex]
[tex]\le k\left|\sin x\right|+\left|\sin x\right|=(k+1)\left|\sin x\right|[/tex]
This is the inequality for [tex]n=k+1[/tex], so by induction it holds for every natural [tex]n[/tex] and every real [tex]x[/tex].

Solution:
Let [tex]z_{n}=x^{n}+\frac{1}{x^{n}}[/tex]. By hypothesis [tex]z_{1}[/tex] is an integer, and
[tex]z_{2}=\left(x+\frac{1}{x}\right)^{2}-2=z_{1}^{2}-2[/tex]
is also an integer. For every natural [tex]n\ge 2[/tex] we have
[tex]z_{1}z_{n}=\left(x+\frac{1}{x}\right)\left(x^{n}+\frac{1}{x^{n}}\right)=x^{n+1}+\frac{1}{x^{n+1}}+x^{n-1}+\frac{1}{x^{n-1}}=z_{n+1}+z_{n-1}[/tex]
i.e.
[tex]z_{n+1}=z_{1}z_{n}-z_{n-1}[/tex]
We use induction with two base cases: [tex]z_{1}[/tex] and [tex]z_{2}[/tex] are integers. Inductive step: assume that [tex]z_{k-1}[/tex] and [tex]z_{k}[/tex] are integers for some [tex]k\ge 2[/tex]. Then [tex]z_{k+1}=z_{1}z_{k}-z_{k-1}[/tex] is an integer as a product and a difference of integers. Hence [tex]x^{n}+\frac{1}{x^{n}}[/tex] is an integer for every natural [tex]n[/tex].

Solution:
Let [tex]R_{n}[/tex] be the number of parts. One circle divides the plane into [tex]R_{1}=2[/tex] parts (inside and outside). Suppose [tex]k\ge 1[/tex] circles are drawn and we add the [tex](k+1)[/tex]-th circle. It meets each of the [tex]k[/tex] old circles at exactly two points, and these [tex]2k[/tex] points are all different, because no three circles pass through one point. They divide the new circle into [tex]2k[/tex] arcs.
No arc contains intersection points in its interior, so each arc lies inside one of the existing parts and divides it into two. Hence each arc adds exactly one part:
[tex]R_{k+1}=R_{k}+2k[/tex]
This gives
[tex]R_{1}=2, \quad R_{2}=4, \quad R_{3}=8, \quad R_{4}=14[/tex]
and we prove [tex]R_{n}=n^{2}-n+2[/tex] by induction. Base case: [tex]R_{1}=1-1+2=2[/tex]. Inductive step: if [tex]R_{k}=k^{2}-k+2[/tex] for some natural [tex]k[/tex], then
[tex]R_{k+1}=k^{2}-k+2+2k=k^{2}+k+2=(k+1)^{2}-(k+1)+2[/tex]
So the circles divide the plane into [tex]n^{2}-n+2[/tex] parts. Note that [tex]2^{n}[/tex] agrees with the first three values but gives [tex]16[/tex] instead of [tex]14[/tex] for [tex]n=4[/tex], so a guessed pattern must always be proved.

Solution:
We check small values. For [tex]n=1[/tex] the inequality [tex]2\gt 1[/tex] holds, but for [tex]2\le n\le 9[/tex] it fails, since the values of [tex]2^{n}[/tex] and [tex]n^{3}[/tex] are
[tex]4\lt 8, \quad 8\lt 27, \quad 16\lt 64, \quad 32\lt 125, \quad 64\lt 216, \quad 128\lt 343, \quad 256\lt 512, \quad 512\lt 729[/tex]
Since the inequality fails for [tex]n=9[/tex], we need [tex]n_{0}\ge 10[/tex]. We prove by induction that it holds for every [tex]n\ge 10[/tex]. Base case:
[tex]2^{10}=1024\gt 1000=10^{3}[/tex]
Inductive step: assume that [tex]2^{k}\gt k^{3}[/tex] for some [tex]k\ge 10[/tex]. Then, since [tex]k\ge 10[/tex],
[tex]2^{k+1}=2\times 2^{k}\gt 2k^{3}=k^{3}+k\times k^{2}\ge k^{3}+10k^{2}[/tex]
Moreover, [tex]3k^{2}\ge 3k[/tex] and [tex]4k^{2}\ge 1[/tex], so
[tex]10k^{2}=3k^{2}+3k^{2}+4k^{2}\ge 3k^{2}+3k+1[/tex]
Hence
[tex]2^{k+1}\gt k^{3}+3k^{2}+3k+1=(k+1)^{3}[/tex]
So the inequality holds for every [tex]n\ge 10[/tex], and the smallest such number is [tex]n_{0}=10[/tex].

Solution:
A sum of [tex]k[/tex] cents can be paid exactly when [tex]k=5x+7y[/tex] with non-negative integers [tex]x[/tex] and [tex]y[/tex]. The sum [tex]23[/tex] cannot be paid: since [tex]7y\le 23[/tex], we have [tex]y\in\left\{0, 1, 2, 3\right\}[/tex], and
[tex]23-7y\in\left\{23, 16, 9, 2\right\}[/tex]
and none of these numbers is divisible by [tex]5[/tex]. Hence [tex]Z\ge 24[/tex]. We prove by induction that every sum [tex]k\ge 24[/tex] can be paid. Base case:
[tex]24=2\times 5+2\times 7[/tex]
Inductive step: assume that [tex]k=5x+7y[/tex] with integers [tex]x,y\ge 0[/tex] for some [tex]k\ge 24[/tex]. If [tex]y\ge 2[/tex], we replace two [tex]7[/tex]-cent stamps ([tex]14[/tex] cents) with three [tex]5[/tex]-cent stamps ([tex]15[/tex] cents):
[tex]k+1=5(x+3)+7(y-2)[/tex]
If [tex]y\le 1[/tex], then [tex]5x=k-7y\ge 24-7=17[/tex], so [tex]x\ge 4[/tex]; we replace four [tex]5[/tex]-cent stamps ([tex]20[/tex] cents) with three [tex]7[/tex]-cent stamps ([tex]21[/tex] cents):
[tex]k+1=5(x-4)+7(y+3)[/tex]
In both cases [tex]k+1[/tex] can be paid. Therefore every sum [tex]k\ge 24[/tex] can be paid, while [tex]23[/tex] cannot, so [tex]Z=24[/tex].

Solution:
Let
[tex]P_{n}=\frac{1}{2}\times \frac{3}{4}\times \ldots\times \frac{2n-1}{2n}[/tex]
A direct induction does not work: from [tex]P_{k}\lt\frac{1}{\sqrt{3k-1}}[/tex] we would need
[tex]\frac{2k+1}{(2k+2)\sqrt{3k-1}}\le\frac{1}{\sqrt{3k+2}}\iff(2k+1)^{2}(3k+2)\le(2k+2)^{2}(3k-1)[/tex]
[tex]\iff 12k^{3}+20k^{2}+11k+2\le 12k^{3}+20k^{2}+4k-4[/tex]
which is false. So we prove the stronger statement
[tex]P_{n}\le\frac{1}{\sqrt{3n+1}}\qquad(*)[/tex]
for every natural [tex]n[/tex]; its stronger hypothesis makes the inductive step work. Base case: [tex]P_{1}=\frac{1}{2}=\frac{1}{\sqrt{4}}[/tex].
Inductive step: assume that [tex]P_{k}\le\frac{1}{\sqrt{3k+1}}[/tex] for some natural [tex]k[/tex]. Then
[tex]P_{k+1}=P_{k}\times \frac{2k+1}{2k+2}\le\frac{2k+1}{(2k+2)\sqrt{3k+1}}[/tex]
It suffices to show that the right side is at most [tex]\frac{1}{\sqrt{3k+4}}[/tex]. Both sides are positive, so this is equivalent to the inequality between their squares:
[tex]\frac{2k+1}{(2k+2)\sqrt{3k+1}}\le\frac{1}{\sqrt{3k+4}}\iff(2k+1)^{2}(3k+4)\le(2k+2)^{2}(3k+1)[/tex]
[tex]\iff 12k^{3}+28k^{2}+19k+4\le 12k^{3}+28k^{2}+20k+4\iff 0\le k[/tex]
which is true. Hence [tex]P_{k+1}\le\frac{1}{\sqrt{3k+4}}=\frac{1}{\sqrt{3(k+1)+1}}[/tex], and (*) holds for every natural [tex]n[/tex]. Finally, for [tex]n\gt 1[/tex] we have [tex]3n+1\gt 3n-1\gt 0[/tex], so
[tex]P_{n}\le\frac{1}{\sqrt{3n+1}}\lt\frac{1}{\sqrt{3n-1}}[/tex]

Solution:
Let [tex]A_{n}=82^{n+1}+(45n-82)\times 127^{n}[/tex] and note that [tex]127-82=45[/tex]. We use induction on [tex]n[/tex]. Base case:
[tex]A_{1}=82^{2}+(45-82)\times 127=6724-4699=2025=45^{2}[/tex]
To relate [tex]A_{k+1}[/tex] to [tex]A_{k}[/tex], we compute (using [tex]45(k+1)-82=45k-37[/tex])
[tex]A_{k+1}-82A_{k}=82^{k+2}+(45k-37)\times 127^{k+1}-82^{k+2}-82(45k-82)\times 127^{k}[/tex]
[tex]=127^{k}\left[127(45k-37)-82(45k-82)\right][/tex]
The expression in brackets equals
[tex]45k(127-82)-127\times 37+82^{2}=45^{2}k-4699+6724=2025k+2025=45^{2}(k+1)[/tex]
Thus
[tex]A_{k+1}=82A_{k}+45^{2}(k+1)\times 127^{k}[/tex]
Inductive step: assume that [tex]A_{k}[/tex] is divisible by [tex]45^{2}[/tex] for some natural [tex]k[/tex]. Then both terms on the right are divisible by [tex]45^{2}[/tex], so [tex]A_{k+1}[/tex] is divisible by [tex]45^{2}[/tex]. By induction, [tex]A_{n}[/tex] is divisible by [tex]45^{2}[/tex] for every natural [tex]n[/tex].

Solution:
We prove by induction on [tex]n[/tex] that the red part can be covered for every position of the blue square. Base case: for [tex]n=1[/tex] the square has side [tex]2[/tex], and its red part consists of three unit squares that form exactly one L-tromino.
Inductive step: assume that for some natural [tex]k[/tex] every square of side [tex]2^{k}[/tex] with one arbitrary unit square excluded can be covered with L-trominoes. Divide a square of side [tex]2^{k+1}[/tex] by the segments joining the midpoints of its opposite sides into four quadrants, squares of side [tex]2^{k}[/tex]. The blue square lies in exactly one quadrant.
Each of the other three quadrants has a corner unit square at the centre of the big square; these three unit squares form an L-tromino, and we place one tromino on them. Now each of the four quadrants is a square of side [tex]2^{k}[/tex] with exactly one excluded unit square (the blue one, or the one covered by the central tromino).
By the induction hypothesis each quadrant can be covered, and together with the central tromino this covers the whole red part. Hence the statement holds for every natural [tex]n[/tex]. This agrees with the number of red unit squares: [tex]4^{n}-1[/tex] is divisible by [tex]3[/tex].