Prove by strong induction that $2^n$ divides $p_n$ for all integers n ≥ 1

Question

Let $p_1 = 4$, $p_2 = 8$, and $p_n = 6p_{n−1} − 4p_{n−2}$ for each integer $n ≥ 3$.
Prove by strong induction that $2^n$ divides $p_n$ for all integers $n ≥ 1$

I got up to the base step where by you prove for $p_3$ but unsure about the strong induction step

Answer 1

Hint:

If by inductive hypothesis $2^{n-1}\mid a_{n-1}$, then $\,2\cdot2^{n-1}\mid 6\cdot a_{n-1}$.

Likewise if by inductive hypothesis $2^{n-2}\mid a_{n-2}$, then …

Answer 2

Let $p_m = k_m 2^m$ for $m< n$ and $k_m$ an arbitrary sequence. We can assume this as the hypothesis. Then $$p_n = 6p_{n-1} - 4p_{n-2} = 3\cdot 2\cdot k_{n-1} 2^{n-1} - 2^2 \cdot k_{n-2} 2^{n-2} = 2^n \cdot (3k_{n-1} - k_{n-2})$$ This also gives $k_n = (3k_{n-1} - k_{n-2})$ as a byproduct.

Answer 3

For $p_1$ and $p_2$ the statement is true. Now suppose that the statement is true for $p_k$, for all $k<n$, and we want to prove it for $k=n$.

$p_n=6p_{n-1}-4p_{n-2}$; by strong induction $p_{n-1}=2^{n-1}a$ and $p_{n-2}=2^{n-2}b$ for some integers $a$ and $b$. Then

$p_n=6p_{n-1}-4p_{n-2}=6(2^{n-1}a)-4(2^{n-2}b)=3\cdot 2^na-2^nb=2^n(3a-b)$

so $p_n$ is divisible by $2^n$, as we wanted to see.

Answer 4

If $2^n$ divides $p_n$ then we have that $p_n = \lambda_n 2^n$ for some integer $\lambda_n$. Therefore, the inductive hypothesis states that:

$$ p_n = \lambda_n2^n = 6p_{n - 1} - 4p_{n - 2} $$

If we assume that it holds for both $n - 1$ and $n - 2$ (this is the strong induction) then we get that: $p_{n - 1} = \lambda_{n - 1}2^{n - 1}$ and $p_{n - 2} = \lambda_{n - 2}2^{n - 2}$. Putting this together we find that:

\begin{align} 6p_{n - 1} - 4p_{n - 2} =&\ 6\lambda_{n - 1}2^{n - 1} - 4\lambda_{n - 2}2^{n - 2}\\ =&\ 2^n \left(\frac{6\lambda_{n - 1}}{2^1} - \frac{4\lambda_{n - 2}}{2^2}\right) \\ =& 2^n \left(\frac{6}{2}\lambda_{n - 1} - \frac{4}{4}\lambda_{n - 2}\right) \\ =&\ 2^n \left(3\lambda_{n - 1} - \lambda_{n - 2}\right) \end{align}

Therefore $2^n$ divides $p_n$ by a factor of $3\lambda_{n - 1} - \lambda_{n - 2}$ (which are both assumed to be integers through the inductive hypothesis).