Define a sequence as follows:
a(0) = 2
a(n+1) = 2a(n) + √ 3a(n)2 - 12
show that all the members of this sequence are integers
Let's start by looking at a few elements of the sequence:
2 4 14 52 194 724 2702 10084 37634 140452
It appears that once the sequence gets started, each term is approximately four times the previous term, and if we look closer, it appears that the difference between four time one term and next term is actually the previous term!. So the following seems to describe the sequence, at least for the first 10 terms:
b(0) = 2
b(1) = 4
b(n+1) = 4b(n) - b(n-1)
What we'd like to do now is show that a(n) = b(n) for all n, since from the recurrence equation above, the b(n) values are clearly all integers.
Let's get a closed form expression for b(n). The usual approach for recurrence equations of this form is to try a solution b(n) = Kxn, and try to find K and x to give the required values.
Substituting into the recurrence equation, we get:
Kxn+1 = 4Kxn - Kxn-1
or
x2 - 4x + 1 = 0
This has two solutions: 2 + √3 and 2 - √3. Any linear combination of powers of those values will also satisfy the recurrence equation, so in general b(n) = K(2 + √3)n + L(2 - √3)n
We can determine K and L from the initial conditions:
2 = b(0) = K + L
4 = b(1) = K(2 + √3) + L(2 - √3) = 2(K + L) + √3(K - L) = 4 + √3(K - L)
So K = L = 1, and b(n) = (2 + √3)n + (2 - √3)n
Now we can show that b(n) = a(n) for all n, by showing that b(n) satisfies the same recurrence equation and
initial conditions as a(n).
The initial conditions are easy:
b(0) = 2 = a(0).
For the recurrence equation, we want to show that:
b(n+1) = 2b(n) + √ 3b(n)2 - 12
Starting with the left hand side: LHS = b(n+1) = (2 + √3)n+1 + (2 - √3)n+1
And the right hand side:
RHS = 2b(n) + √ 3b(n)2 - 12
= 2(2 + √3)n + 2(2 - √3)n + √ 3((2 + √3)n + (2 - √3)n)2 - 12
= 2(2 + √3)n + 2(2 - √3)n + √ 3((2 + √3)2n + (2 - √3)2n + 2) - 12
= 2(2 + √3)n + 2(2 - √3)n + √ 3((2 + √3)2n + (2 - √3)2n - 2)
= 2(2 + √3)n + 2(2 - √3)n + √ 3((2 + √3)n - (2 - √3)n)2
= 2(2 + √3)n + 2(2 - √3)n + √3((2 + √3)n - (2 - √3)n)
= (2 + √3)n+1 + (2 - √3)n+1
= RHS
So b(n) = a(n) for all n. Since the b(n) are clearly all integers, so are all the a(n).