Question

About Prove each of the following statements using mathematical induction. (a) Define the sequence {cn} as follows: c0 = 5 ck = (ck-1)2 for k ≥ 1 Prove that for n ≥ 0, cn = 52n. Note that in the explicit formula for cn, the exponent of 5 is 2n. (b) Define the sequence {bn} as follows: b0 = 1 bk = 2bk-1 + 1 for k ≥ 1 Prove that for n ≥ 0, bn = 2n+1 - 1.

Answer 1

a.

$\begin{cases}c_0=5\\c_n={c_{n-1}}^2&\text{for }n\ge1\end{cases}$

For $n=1$, we have by this definition $c_1={c_0}^2=5^2$ which is equal to $5^{2^n}$ for $n=1$.

Assume $c_n=5^{2^n}$ for some $n=k$. We want to use this to show that this implies $c_{k+1}=5^{2^{k+1}}$. By the recursive definition,

$c_{k+1}={c_k}^2=(5^{2^k})^2=5^{2^{k+1}}$

and we're done.

b.

$\begin{cases}b_0=1\\b_n=2b_{n-1}+1&\text{for }n\ge1\end{cases}$

For $n=0$, we have $b_0=1$, and $2^{n+1}-1=1$.

Assume $b_n=2^{n+1}-1$ for some $n=k$. Then for $n=k+1$, we have

$b_{k+1}=2b_k+1=2\left(2^{k+1}-1\right)+1=2^{k+2}-1$

and we're done.