Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
so is that all I have to show? It is clear that 3∣6bn−2: we don't even need any information about bn−2 to see that. It follows that 3∣(6bn−2+bn−1) (if 3∣x and 3∣y then 3∣(x+y). So i just write that and then Therefor it is shown that 3| =b_n for all integers n >=1 by strong induction. It just seems too easy for a 5mark question? But thank you –  Ghozt Apr 25 '13 at 4:51
    
You are expected to write it up in "strong induction" style, roughly like I did. –  André Nicolas Apr 25 '13 at 5:00
    
Nicolas. Thank you. –  Ghozt Apr 25 '13 at 10:46
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.