# How to prove $a_{n} < 2$ if $\displaystyle a_{n+2}=a_{n+1}+\frac{a_{n}}{3^n}$

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.$$

-
Great answer! For your induction hypothesis on $n\geq 3$, you might want to assume that $a_k<2$ for all $k=1,\ldots,n$. – 1015 Jan 26 '13 at 21:06
Thanks, that's what I meant. – Mercy King Jan 26 '13 at 21:16

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}$$

-
+1. I started writing an answer similar to yours before I saw you posted this. It might be easier to prove $$a_n < 2 - \dfrac9{3^n}$$ – user17762 Jan 26 '13 at 21:21

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}$$

-
I need an answers without derivatives:) – Iuli Jan 26 '13 at 20:50
asymptotically the difference equation is equivalnet to $y'(x)=3^{-x}y(x)$ solving this i get that $a(n) \sim exp( -3^{-n}/log(3))$ – Jose Garcia Jan 26 '13 at 20:55