# 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?

#### Solutions Collecting From Web of "Proving by strong induction for a sequence of integers, $2^n$ divides term $n$"

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$.