Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers 3

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|improve this answer
1  
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 Jan 26 '13 at 21:16
add comment

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

share|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
add comment

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|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
add comment

Your Answer

 
discard

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.