1. ## Induction

$\displaystyle f:\mathbb{N}\rightarrow\mathbb{N}$
$\displaystyle f(1)=1 \ f(2)=2 \ f(3)=3 \ f(n)=f(n-1)+f(n-2)+f(n-3)$
$\displaystyle \forall n\geq 4$ Prove $\displaystyle f(n)\leq 2^n \ \ \forall n\in\mathbb{N}$
P(1), P(2), P(3), P(4) are all true.
Assume p(k) is true for a fixed but arbitrary $\displaystyle k\geq 4 \ \ k\in\mathbb{Z}$
Prove $\displaystyle P(K+1): \ f(k)+f(k-1)+f(k-2)\leq 2^{k+1}$

I am sort of stuck.

2. Since $\displaystyle P(k-2)$ is true we have $\displaystyle f(k-2)\leq 2^{k-2}$, since $\displaystyle P(k-1)$ is true we have $\displaystyle f(k-1)\leq 2^{k-1}$ and since $\displaystyle P(k)$ is true we have $\displaystyle f(k)\leq 2^{k}$. Now sum these inequalities.

3. Originally Posted by girdav
Since $\displaystyle P(k-2)$ is true we have $\displaystyle f(k-2)\leq 2^{k-2}$, since $\displaystyle P(k-1)$ is true we have $\displaystyle f(k-1)\leq 2^{k-1}$ and since $\displaystyle P(k)$ is true we have $\displaystyle f(k)\leq 2^{k}$. Now sum these inequalities.
$\displaystyle f(k+1)\leq 2^{k-2}+2^{k-1}+2^k=\frac{7}{4}2^k<2^{k+1}$

$\displaystyle \Rightarrow f(k+1)\leq \frac{7}{4}2^k<2^{k+1}\Rightarrow f(k+1)\leq 2^{k+1}$

4. It's ok.