Using strong induction to prove that $f(n+1)=\frac23 f(n)+\frac13 f(n-1)$ is bounded above

Question

Let the sequence

$$f(n+1)=\frac23 f(n)+\frac13 f(n-1),f(0)=5,f(1)=1$$

Then I tried to use weak induction to prove that the sequence is bounded above by $5$ but I dont found an easy way to do it.

Then I remembered something about some stronger version of induction but I never used it. Reading about the topic it seems that fit better to this problem that the weak induction.

Check if my proof is correct please. If I understood correctly the difference between strong and weak induction is that the stronger version change the induction hypothesis to something like

$$P(k),P(k+1),...,P(n)\text{ are true }$$

where $P(k)$ is the base case. Then if $P(n+1)$ is true this implies that $P(n)$ is true for all $n\ge k$ (if I understood correctly).

Then for this case we can see that $f(1)\le 5$. Then I assume in the induction hypothesis that $f(n)\le 5$ such that $1\le n$. Then I must show that under this hypothesis the statement is true for $f(n+1)$.

Then because $f(n+1)=\frac23 f(n)+\frac13 f(n-1)\le \frac23 5+\frac13 5=5$ the proof is complete. It is this proof correct? Correct me if I did something wrong, thank you.

Answer 1

Assuming just $f(n)\leq5$ will not allow you to prove that $f(n+1)\leq5$. On the other hand it is not necessary to assume that $f(k)\leq5$ for all $k\leq n$ in order to perform the induction step. But you can argue as follows (as you hinted at in the final part of your question): Let

$${\cal P}(n):= \bigl(\>f(n-1)\leq 5\quad\wedge\quad f(n)\leq5\>\bigr)\ . $$ Then ${\cal P}(1)$ is true by assumption, and using your argument it is easy to prove that ${\cal P}(n)\Rightarrow{\cal P}(n+1)$ for all $n\geq1$.

Answer 2

Here it is straightforward to find a closed form for $f(n)$, and this allows us to yield stronger conclusions about the sequence.

As a second-order linear homogeneous recurrence relation with constant coefficients, it is known that the solution has the form

$$f(n) = a\cdot r^n + b\cdot s^n $$ where $r$ and $s$ are roots to the characteristic polynomial, $$1 - \frac23z - \frac13z^2. $$ Solve the above, we have $r=1$, $s=-\frac13$. Now, from $f(0)=5$ and $f(1)=1$ we have the system of linear equations \begin{align} a\cdot 1 + b\cdot 1 &= 5\\ a\cdot 1 + b\cdot \left(-\frac13\right) &=1, \end{align} which yields $a=2$, $b=3$. Indeed, we may prove this is a solution by induction (the base cases having just been shown); if $f(n) = 2 + 3\cdot\left(-\frac13\right)^n$ for some $n\geqslant 1$, then \begin{align} f(n+1) &= \frac23 f(n) + \frac13 f(n-1)\\ &= \frac23\left(2 + 3\cdot\left(-\frac13\right)^n \right) + \frac13\left(2 + 3\cdot\left(-\frac13\right)^{n-1}\right)\\ &= 2 + 2\cdot\left(-\frac13\right)^n + \left(-\frac13\right)^{n-1}\\ &= 2 + \left(-\frac13\right)^{n-1}\left(1-\frac23 \right)\\ &= 2 - \left(-\frac13\right)^n\\ &= 2 + 3 \left(-\frac13\right)^{n+1}. \end{align} It follows that

$$ f(n) = \begin{cases} 2 + 3^{-n+1},& n \text{ even }\\ 2 - 3^{-n+1},& n \text{ odd. }\\ \end{cases} $$ From this it is clear that $1\leqslant f(n)\leqslant 5$ for all $n$, and further that $$\lim_{n\to\infty} f(n)=2. $$