Provided the following sequence of integers $t_1, t_2, t_3$,… is defined as:
$t_1 =4, t_2 =8$ and $t_n= $ $ 6t_n$$_-$$_1$ – $4t_n$$_-$$_2$ for all integers $n \geq 3$
How do we prove that $2^n$ divides $t_n$ for all integers $n \geq 1$ by strong induction?
So far, I am having problems with the induction step as I am still trying to grasp the concept of strong induction, but this is what I came up with so far:
Base step:
$t_3 = 32$, which is divisible by 8; and $t_4 = 160$, which is divisible by 16.
$\therefore$ Statement is true when $n=3$ and $n=4$.
Induction step:
Assuming $k=n$ and the statement is true for $3,4,…k$. Prove that $2^k$ divides $t_k$ for $k+1$:
$t_3 = ((2^3 – 2)(2^3) – (2^2)(2^2)) = 2^6 – 2^4 – 2^4 $; dividing this by $2^3$ gives $2^3 – 2^2$ which would be an integer result.
$t_4 = ((2^3 – 2)(2^5) – (2^2)(2^3)) = 2^8 – 2^6 – 2^5 $; dividing this by $2^4$ gives $2^4 – 2^2 – 2$ which would also be an integer result.
$\therefore$ By the logic above, the statement also holds for $k-1$, $k$ as well as $k+1$, thus as required to prove by strong induction.
I believe this is a fundamentally flawed way of trying to prove by strong induction, but this is the only way I can possibly think of. Can someone show a correct method of solving this?
Best Answer
You need to give a proof for arbitrary $k$, rather than any particular $k$. You have shown that the statement is true for $k = 1, 2, 3, 4$ and no more.
As an example of an inductive argument, assume for the sake of induction that $2^{k-1}$ divides $a_{k-1}$ and $2^{k}$ divides $a_k$. Write this as $a_{k-1} = 2^{k-1}l, a_k = 2^{k}m$.
Then we have
Thus, $2^{k+1}$ divides $a_{k+1}$. This shows inductively that $2^n$ divides $a_n$.