# Proving by strong induction for a sequence of integers, $2^n$ divides term $n$

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?

• $n=1\implies2^n=2\nmid4=t_n$ – barak manos Apr 11 '15 at 5:34
• Hint $\,\ 2^n\mid 6(2^{n-1}),\, 4(2^{n-2})\ \$ – Bill Dubuque Apr 11 '15 at 15:07

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

• $a_{k+1} = 6a_k - 4a_{k-1} = 6(2^{k}m) - 4(2^{k-1}l) = 2^{k+1}(3m-l)$.

Thus, $2^{k+1}$ divides $a_{k+1}$. This shows inductively that $2^n$ divides $a_n$.

Let $u_n = t_n/2^n$, or $t_n = 2^n u_n$.

Since $t_n =6 t_{n-1}-4t_{n-2}$, $2^nu_n =6 \cdot 2^{n-1}u_{n-1}-4\cdot 2^{n-2}u_{n-2} =3 \cdot 2^{n}u_{n-1}- 2^{n}u_{n-2}$, or $u_n =3 u_{n-1}- u_{n-2}$.

Since $u_1$ and $u_2$ are integers ( $u_1 = t_1/2 = 2$ and $u_2 = t_2/4 = 2$ ), all following $u_n$ are integers.

Even more, since $u_1$ and $u_2$ are even integers, so are all following $u_n$.