Let $(a_{n})_{n \geq1}$ be a real sequence such that $a_{1}=a_{2}=1$ and $\displaystyle a_{n+2}=a_{n+1}+\frac{a_{n}}{3^n}, n\geq 1$.
Prove that $a_{n} < 2, \forall n \geq 1.$
I write $$\sum a_{k+2}-a_{k+1}=\sum \frac{a_{k}}{3}$$ and I obtained :
$$3a_{n+2}=a_{1}+\ldots+a_{n}+3$$
or
$$a_{n}=\frac{a_{1}+\ldots+a_{n-2}+3}{3} < 2$$
And what remains to prove it is :
$$a_{1}+\ldots +a_{n-2} < 3,$$ but from this point I don't know how I have to do.
I need a proof without derivatives.
Thanks :)
We have $$ a_1=a_2=1,\ a_3=a_2+\frac{a_1}{3}=\frac43<2. $$ If we assume that $a_k<2$ for all $k=1,\ldots,n$, with $n \ge 3$, then we have $$ a_{n+1}=a_2+\sum_{k=2}^n(a_{k+1}-a_k)=a_2+\sum_{k=2}^n\frac{a_{k-1}}{3^{k-1}}<1+\sum_{k=2}^n\frac{2}{3^{k-1}}=1+1-\frac{1}{3^{n-1}}<2. $$
Claim:
$$a_n < 2-\frac{1}{3^n} \,.$$
$P(1), P(2)$ are easy to check.
Inductive step:
$$a_{n+1}= a_{n+1}+\frac{a_n}{3^n} \leq 2-\frac{1}{3^{n+1}}- \frac{2-\frac{1}{3^n}}{3^n}=2-\frac{1}{3^{n+1}}- \frac{2}{3^n}+\frac{1}{9^n} $$
If we can prove taht
$$2-\frac{1}{3^{n+1}}- \frac{2}{3^n}+\frac{1}{9^n} < 2-\frac{1}{3^{n+2}}$$ we are done.
But this is equivalent to
$$\frac{1}{3^{n+2}}+\frac{1}{9^n} <\frac{1}{3^{n+1}}+ \frac{2}{3^n}$$
which is obvious.
P.S. This is a pretty standard but not well known technique. If $a_n$ is increasing, then $a_n \leq C$ cannot be proven directly by induction, but one might be able to find a decreasing $b_n \geq 0$, and then prove by induction the stronger claim
$$a_n < C-b_n \,.$$
The standard well known example of this phenomena is
$$1+\frac{1}{2^2}+..+\frac{1}{n^2} <2 $$ vs $$1+\frac{1}{2^2}+..+\frac{1}{n^2} <2 -\frac{1}{n+1}$$
if we assume there is a generating function so
$$ f(x)= \sum_{n=0}^{\infty}a_{n}x^{n} $$
then $ f(x) $ satisfy the functional equation
$$ f(x)-a_{0}-a_{1}x=f(x)x-a_{0}x+x^{2}f(x/3) $$
from this i think you could obtaien the derivatives so $$ n!f^{(n)}(0)= a_{n} $$
