Question

Let an be the recurrence defined by: ao = 4.4 = 7, and for all n 2, an-2an-1 + 5an-2. Using constructive induction, find integer constants A and B such that for all n 2 0, an S AB". Try to make B as small as possible.

Answer 1

If we were to use induction we would use the following base cases

$a_0=4\leq A$

and

a1 = 7-AB

now, suppose that the inequality holds for all   (inductive hypothesis )

K k

That is

AB
for all  
K k

Then, we want to prove that it's true for k+1

Since

$a_{k+1}=2a_k + 5a_{k-1}\leq 2AB^{k}+ 5AB^{k-1}$

Then

k+1

so that we can prove the inductive step

Thus, since A and B are positive (this can easily be proven from the base cases) we have

$2AB+ 5A \leq AB^{2}$

$2B+ 5\leq B^{2}$

So we have to solve the inequality

$B^{2}-2B-5\geq 0$

Using the quadratic function we can factorize

2t (-2)2 - 4(-5))

Then

$(B- (1-\sqrt{6}))(B- (1+\sqrt{6}))\geq 0$

both factors must be positive (they can't be both negative since B is positive)

then

B- (1 V6) 0 and B (1V6) 2 0

which yields

$B\geq (1+\sqrt{6})$

Therefore the smallest possible values for A and B are:

$A=4$

$B=1+\sqrt{6}$