Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :



$$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 :)

share|cite|improve this question
up vote 8 down vote accepted

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

share|cite|improve this answer
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


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

share|cite|improve this answer
+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} $$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.