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

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 .

I'm not looking for a full solution just some hints would be great. Thanks

Observe that

Originally Posted by Isomorphism

[snip]

Observe that

Isomorphism,

I don't think that last line is right: it is not true that .

Here is an alternative approach. By the inductive hypothesis,

.

Since a(n) is an integer,

,

so