Strong Mathematical Induction: Prove $3\mid b_n$ for a given recurrence relation $b_n$

Question

Here is what I have so far:

Proof $3\mid b_n$ for $n$ integers $\geq 1$

Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$

$$P(1)=3\mid b_1$$

$$P(1)= 3\mid 3$$

Since $3\mid 3$, the base case is true for $n = 1$.

$$P(2)=3\mid b_2$$

$$P(2)= 3\mid 9$$

Since $3\mid 9$, the base case is true for $n = 2$

We assume that $P(i)$ is true for some integer $i$ $P(i)= 3\mid b_i=3\mid 6b_{i-2}+b_{i-1}$

We will now prove that $P(i+1)$ is true

WTS: $3\mid b_{i+1}=3\mid 6b_{i-1}+b_i$

$$3\mid b_{i+1}= 3\mid 6b_{(i+1)-2}+b_{(i+1)-1}$$

$$3\mid b_{i+1}= 3\mid 6b_{(i-1)}+b_{(i)}$$

$$3\mid b_{i+1}= 3\mid 6b_{(i-1) }+(6b_{i-2}+b_{i-1})$$

How is it even possible to prove this?

Answer 1

We want to show that $3\mid b_i$ for all $i$. We have $b_1=1$, $b_2=9$, and $b_n=6b_{n-2}+b_{n-1}$ for all $n \ge 3$.

We are told to use strong induction, so we write it up in that style. However, ordinary induction works just as quickly.

For the strong induction step, we need to show that if $3\mid b_k$ for all $k\lt n$, then $3\mid b_n$.

We use the recurrence $b_n=6b_{n-2}+b_{n-1}$. Since $n-1\lt n$, we have by the induction hypothesis that $3\mid b_{n-1}$.

It is clear that $3\mid 6b_{n-2}$: we don't even need any information about $b_{n-2}$ to see that.

It follows that $3\mid (6b_{n-2}+b_{n-1})$ (if $3\mid x$ and $3\mid y$ then $3\mid (x+y)$, and we are finished.

Remarks: $1.$ If our recurrence had been $b_n=5b_{n-2}+b_{n-1}$, with the same initial conditions $b_1=3$, $b_2=9$, we could use a similar argument to deduce that $3\mid b_n$ for all $n$. But in the induction step, we would have to use the fact that since $n-2\lt n$ and $n-1\lt n$, we have $3\mid b_{n-2}$ and $3\mid b_{n-1}$.

$2.$ It is important to see that there is nothing much going on here. The number $3$ divides $b_1$ and $b_2$. But because $b_3=6b_1+b_2$, it follows that $3$ divides $b_3$. Then because $b_4=6b_2+b_3$, it follows that $3$ divides $b_4$. And so on forever.

Answer 2

One way of induction (let's call this the ordinary induction). You start with hypothesis $P_1$ and show that it is true. Then, you assume $P_n,\,n\geq 1$ holds and then show that $P_{n+1}$ holds. This is like you prove $P_1$, the inductive steps allows you to prove $P_2$ from $P_1$, and then $P_3$ from $P_2$ and so on. This is I guess what you tried and got stuck at.

But, you can also take a different path. You may start by proving that $P_1$ and $P_2$ are true by hand, and then use induction as follows: For $n \geq 3$, prove that $P_n$ holds assuming that $P_{n-1}$ and $P_{n-2}$ holds. In such a scenario, you use $P_1$ and $P_2$ to prove $P_3$, and then $P_2$ and $P_3$ to prove $P_4$, and so on. This is roughly called complete induction, as you are not only using $P_{n-1}$ for proving $P_n$, but you are also using $P_{n-2}$ (in general, you may use the ones before $P_{n-2}$, e.g. $P_{n-3}$). The two forms of induction are equivalent.

In your case, you have already realized that assuming $P_{n-1}$ does not immediately give you $P_n$ (ordinary induction does not work). Hence, per André's suggestion (after showing $P_1$ and $P_2$ by hand as you have done) you assume both $P_{n-1}$ and $P_{n-2}$ holds for $n \geq 3$, and then the proof becomes easy.