Stron induction, multiple choice not sure how he got his answer

[mr_coffee]

Hello everyone, I'm confused on what the answer is here, it looks like he circled every answer but i don't see how that's possible. So maybe he cirlced c and b and marked a and b wrong. http://suprfile.com/src/1/3pyqpub/lastscan.jpg How would I test to verify that c and d are correct?
if b1 = 3, b2 = 6 and b_n = b_n-1 + b_n=2
for all integgers n >= 3.

n has to be >= 1, so do I plug in
n = 1, n = 2, and n = 3?

like n = 1, so b_n = b_0 + b_n-1

But b_0 and b_n-1 isn't even listed so I am not sure where to go from this.

 

[HallsofIvy]

Yes, all four of those are correct. (You would, of course, have to verify that b₁ is divisible by 3 and, for b, that b₂ is divisible by 3, for a and c, that both b₂ and b₃ are divisible by 3.

like n = 1, so b_n = b_0 + b_n-1

But b_0 and b_n-1 isn't even listed so I am not sure where to go from this.

There is no b_0: the sequence starts with b_1. The first one you would have to calculate is b_3= b_1+ b_2= 3+ 6= 9 which is divisible by 3.

It really doesn't matter where you start the "induction step", as long as you have verified the statement separately for each n less than that.

Of course, if it is true that "a_i is divisible by 3 for all $i\le k$" then we can write a_k= 3m and a_k-1= 3n for some integers m and n. Then a_k+1= a_k+ a_k-1= 3n+ 3m= 3(n+m), a multiple of 3.

 

[mr_coffee]

Thanks Ivy, i'll take another look at it!

 

[0rthodontist]

c and d are correct, a and b are not correct.
The problem with a is that you start the induction on k > 3. It doesn't check to see if it's true for k = 3.
The problem with b is that you assume the statement is true for all i <= k. So you assume it's true when i = k and then you show that it's true for k--circular logic.

 

[mr_coffee]

THanks for the responce!
i'm confused on how you figure out ur boundaries...
how do u know which boundary is correct or incorrect for i and also how did u know what k to test for? I was able to figure out easy problems using induction but I'm quite lost when it comes to strong induction on how you set up your base case and step. any guidance would be great!