1

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

Jonas Meyer
  • 53,602
dave
  • 103
  • You don't really need strong induction, though it does not hurt of course. Consider pairs $(p_n,p_{n-1})$ and simple induction will do. – Jean-Claude Arbaut Apr 15 '15 at 08:49
  • @Jean-ClaudeArbaut Technically this does require "strong" induction which simply means you require more than the previous result. Frankly, I see very little difference between weak and strong induction, but this does require knowing more than merely the previous result. – Jared Apr 15 '15 at 08:52
  • @Jared Well, not really, since using pairs, all you need is in the previous pair. It's even the standard way to change an order $n$ linear recurrence on scalars, into an order $1$ recurrence on a vector with $n$ elements. – Jean-Claude Arbaut Apr 15 '15 at 08:54
  • @Jean-ClaudeArbaut Like I said, I see little difference between weak vs. strong induction--your statement proves that (imo). In my opinion you are basically saying the two are equivalent (if we start using vectors). The one difference might come where we must use all previous values rather than a subset--but I cannot come up with such an example (except maybe prime numbers) off the top of my head. – Jared Apr 15 '15 at 09:00
  • 1
    @Jared: I'd say that if you "can't predict" which lower values you'll need, then you're going to use strong induction, and this is often the case for examples where you'll factorise $n+1$ in the inductive step. If you can predict that you just need a specified range of values, especially like this where the "range" is two adjacent values, then you can get away with calling it weak induction. But for most purposes strong induction is just weak induction with a particular form of the predicate, it has $\forall m \le n$ in it. So whatever ;-) – Steve Jessop Apr 15 '15 at 10:00

4 Answers4

6

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.

mathifold.org
  • 939
4

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.

AlexR
  • 24,905
3

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 …

Bernard
  • 175,478
1

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

Jared
  • 6,227