6.7. Solutions Recursive Definitions

Solutions to Section 3.7

Solution to Exercise (1†)

Proof: We prove this once again by induction.

• Base Case: When $n=0$ and when $n=1$, the statement is clearly true, since $f_0=0<1=2^0$ and $f_1=1<2=2^1$, so $f_0<2^0$ and $f_1<2^1$.

• Inductive Case: If we now take an arbitrary $k$ such that $k\ge 2$, we assume that $f_n<2^n$ for $n=k-1$ and $n=k-2$ holds. To complete the induction, we need to show that $f_k<2^k$ is also true:

  $$\begin{array}{r}\begin{array}{rl}{f}_k& =f_{k-1}+f_{k-2}\\ & <2^{k-1}+2^{k-2}& \text{(inductive hypothesis)}\\ & =\frac{2^k}{2}+\frac{2^k}{4}\\ & =\frac{3}{4}\cdot 2^k\\ & <2^k\end{array}\end{array}$$

  This shows that $f_k<2^k$ is true, which completes the induction.

Solution to Exercise (2†)

Proof: We prove the equation using induction.

• Base Case: When $n=1$, $a_1=1\cdot 2^{1-1}$ is true since both sides are equal to 1.

• Inductive Case: Let $k\ge 1$ be an arbitrary integer. We asssume that $a_n=n{2}^{n-1}$ holds for $n=k-1$. To complete the induction, we need to show that the equation also holds for $n=k$.

  $$\begin{array}{r}\begin{array}{rl}{a}_k& =2a_{k-1}+2^{k-1}\\ & =2(k-1)2^{k-1-1}+2^{k-1}& \text{(inductive hypothesis)}\\ & =(k-1)2^{k-1}+2^{k-1}\\ & =((k-1)+1)2^{k-1}\\ & =k{2}^{k-1}\end{array}\end{array}$$

  Which proves that the equation also holds for $n=k$. Thereby the induction is completed.