# Help with a recursively defined sequence

• Jan 15th 2009, 05:54 PM
LexMiguel
Help with a recursively defined sequence
Hi,

So my problem is as follows:

I have a recursively defined sequence with a(1)=5, and a(n+1)=a(n)^2-a(n). The problem is to show that a(n)>2^2^n for all n>=1.

Proof by Induction:

Base: a(1) = 5 > 4 = 2^2^1, so it's true for n=1.

Induction: a(n+1)=a(n)^2-a(n)>(2^2^n)^2-(2^2^n) and this is where I get stuck. Try as I might I can't seem to show that a(n+1)>2^2^(n+1).

Any help will be much appreciated, and I'm not looking for a full solution just some hints would be great. Thanks
• Jan 16th 2009, 12:08 AM
Isomorphism
Quote:

Originally Posted by LexMiguel
Hi,

So my problem is as follows:

I have a recursively defined sequence with a(1)=5, and a(n+1)=a(n)^2-a(n). The problem is to show that a(n)>2^2^n for all n>=1.

Proof by Induction:

Base: a(1) = 5 > 4 = 2^2^1, so it's true for n=1.

Good. This part is right, however....

Quote:

Induction: a(n+1)=a(n)^2-a(n)>(2^2^n)^2-(2^2^n)
This step is wrong. Note the negative sign does not preserve the inequality. So you cant say \$\displaystyle a(n)^2-a(n)>(2^{2^n})^2-2^{2^n}\$.

Quote:

I'm not looking for a full solution just some hints would be great. Thanks
Observe that \$\displaystyle a(n+1) > a(n) ^2 = (2^{2^n})^2 = 2^{2^{n+1}}\$
• Jan 17th 2009, 09:21 AM
awkward
Quote:

Originally Posted by Isomorphism
[snip]

Observe that \$\displaystyle a(n+1) > a(n) ^2 = (2^{2^n})^2 = 2^{2^{n+1}}\$

Isomorphism,

I don't think that last line is right: it is not true that \$\displaystyle a(n+1) > a(n) ^2 \$.

Here is an alternative approach. By the inductive hypothesis,

\$\displaystyle a(n) > 2^{2^n}\$.

Since a(n) is an integer,

\$\displaystyle a(n) \geq 2^{2^n} + 1\$,

so

\$\displaystyle a(n+1) = a(n) \; [a(n) - 1] \geq (2^{2^n} + 1) [2^{2^n}] > (2^{2^n})^2 = 2^{2^{n+1}}\$