Induction and sequences

Two sequences: $\displaystyle {a_n}={n^2+2n}$, and $\displaystyle {b_1}={3}$, $\displaystyle {b_{n+1}}={b_n+2n+3}$.

• $\displaystyle {a_1}={3}={b_1}$; $\displaystyle {a_2}={8}$ and $\displaystyle {b_2}={3+5}={8}$; $\displaystyle {a_3}={15}$ and $\displaystyle {b_3}={8+7}={15}$.
• Is $\displaystyle {a_n}={b_n}$ for every $\displaystyle n$? Checking cases is no proof. The proof below proves it by induction: if the terms are equal in place $\displaystyle k$, they are equal in place $\displaystyle k+1$ too.

In the lesson on recursion rules we guessed that the sequence $\displaystyle {a_1}={3}$, $\displaystyle {a_{n+1}}={2a_n-1}$ is $\displaystyle {a_n}={2^n+1}$. Now we prove it:

• Base case: $\displaystyle {2^1+1}={3}={a_1}$.
• Inductive step: assume that $\displaystyle {a_k}={2^k+1}$. By the recursion rule $\displaystyle {a_{k+1}}={2a_k-1}={2(2^k+1)-1}={2^{k+1}+1}$ – the formula for $\displaystyle k+1$.
• Conclusion: by the principle of induction, $\displaystyle {a_n}={2^n+1}$ for every natural $\displaystyle n$.

The formula $\displaystyle {a_n}={a_1+(n-1)d}$ is proved by induction from the recursion rule $\displaystyle {a_{n+1}}={a_n+d}$ too:

• Base case: $\displaystyle {a_1+0\cdot d}={a_1}$.
• Inductive step: if $\displaystyle {a_k}={a_1+(k-1)d}$, then $\displaystyle {a_{k+1}}={a_k+d}={a_1+kd}$ – the formula for $\displaystyle k+1$.

The explanation “add $\displaystyle d$ exactly $\displaystyle n-1$ times” is the same proof, without the parts named.

The triangular number $\displaystyle T_n$ is the number of dots in a triangle whose bottom row has $\displaystyle n$ dots.

• Triangle $\displaystyle n+1$ is triangle $\displaystyle n$ and one more row of $\displaystyle n+1$ dots: $\displaystyle {T_1}={1}$, $\displaystyle {T_{n+1}}={T_n+(n+1)}$.
• The formula by place: $\displaystyle {T_n}={\frac{n(n+1)}{2}}$ – and its proof by induction is the proof of the sum of the natural numbers.

A sequence is defined by the recursion rule $\displaystyle {a_1}={2}$, $\displaystyle {a_{n+1}}={a_n+4n+2}$.
Prove by induction that $\displaystyle {a_n}={2n^2}$ for every natural $\displaystyle n$.

By the recursion rule and the induction hypothesis $\displaystyle {a_{k+1}}={2k^2+4k+2}$. Factorise, and reach $\displaystyle 2(k+1)^2$:

A sequence is defined by the recursion rule $\displaystyle {a_1}={3}$, $\displaystyle {a_{n+1}}={3a_n-2}$.

Write the first four terms, and guess a formula by place. (A hint: subtract 1 from each term.)

Prove the guess by induction. In the step, put the hypothesis into the recursion rule:

The pentagonal numbers: $\displaystyle {P_1}={1}$, $\displaystyle {P_{n+1}}={P_n+3n+1}$ (that is $\displaystyle 1, 5, 12, 22, \ldots$).
Prove by induction that $\displaystyle {P_n}={\frac{n(3n-1)}{2}}$ for every natural $\displaystyle n$.

By the recursion rule and the induction hypothesis $\displaystyle {P_{k+1}}={\frac{k(3k-1)}{2}+3k+1}$. Reach $\displaystyle \frac{(k+1)(3k+2)}{2}$:

$\displaystyle L(n)$ is the number of parts into which $\displaystyle n$ lines divide the plane, when no two of them are parallel and no three pass through one point.

Count $\displaystyle L(1)$, $\displaystyle L(2)$, $\displaystyle L(3)$ in the picture, and find $\displaystyle L(4)$.

Line number $\displaystyle n+1$ crosses the $\displaystyle n$ lines before it at $\displaystyle n$ points, so it passes through $\displaystyle n+1$ parts and cuts each of them in two. Write a recursion rule for $\displaystyle L(n)$.

Prove by induction that $\displaystyle {L(n)}={1+\frac{n(n+1)}{2}}$. In the step:

A sequence is defined by the recursion rule $\displaystyle {a_1}={1}$, $\displaystyle {a_{n+1}}={\frac{a_n}{1+a_n}}$.
Work out $\displaystyle a_2$ and $\displaystyle a_3$, guess a formula by place, and prove it by induction. In the step: