# Math Help - Help with a recursively defined sequence

1. ## 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

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

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 $a(n)^2-a(n)>(2^{2^n})^2-2^{2^n}$.

I'm not looking for a full solution just some hints would be great. Thanks
Observe that $a(n+1) > a(n) ^2 = (2^{2^n})^2 = 2^{2^{n+1}}$

3. Originally Posted by Isomorphism
[snip]

Observe that $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 $a(n+1) > a(n) ^2$.

Here is an alternative approach. By the inductive hypothesis,

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

Since a(n) is an integer,

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

so

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