Proof by induction: contradicting result?

[syncmaster913n]

So I have 3^n + 3^n is divisible by 6 and I'm supposed to prove that by induction. First I checked to make sure that this holds true for n = 1:

3^1 + 3^1 = 3 + 3 = 6, wich is clearly divisible by 6. Now for the induction, here is what I did:

3^n + 3^n = 6m (where m is some integer). Working with the left side of the equation:

\(\displaystyle 3^{n+1}\, +\, 3^{n+1}\, =\, 3\,(3^n)\, +\, 3\,(3^n)\, \)

. . .\(\displaystyle =\, 3\,(3^n\, +\, 3^n)\, =\, 3\, (6m)\, =\, 18m\)

Which is divisible by 6. At this point I thought to myself "well, proof done!". But then I realized that 3^0 + 3^0 = 2, which is not divisible by 6. I'm assuming I made some newbie error in the induction part, so could someone point it out to me please?

 

[pka]

So I have 3^n + 3^n is divisible by 6 and I'm supposed to prove that by induction.

Why induction? \(\displaystyle 3^n+3^n=2 \cdot 3^n=6 \cdot 3^{n-1}\)

 

[syncmaster913n]

Thank you for this. The task was to do it by induction so that's what I attempted. Still, I'm not sure your solution disperesed my confusion, since when n = 0 then the result of the multiplication is clearly not divisible by 6. What am I missing?

 

[pka]

Thank you for this. The task was to do it by induction so that's what I attempted. Still, I'm not sure your solution disperesed my confusion, since when n = 0 then the result of the multiplication is clearly not divisible by 6. What am I missing?

It is a common mistake made by ill-prepared mathematics teachers to insist that induction must begin with \(\displaystyle n=0 \text{ or }n=1~\). That is just not the case. The main idea is to prove a statement is true for some integer and also true for each integer thereafter.

 

[Harry_the_cat]

So I have 3^n + 3^n is divisible by 6 and I'm supposed to prove that by induction. First I checked to make sure that this holds true for n = 1:

3^1 + 3^1 = 3 + 3 = 6, wich is clearly divisible by 6. Now for the induction, here is what I did:

3^n + 3^n = 6m (where m is some integer). Working with the left side of the equation:

\(\displaystyle 3^{n+1}\, +\, 3^{n+1}\, =\, 3\,(3^n)\, +\, 3\,(3^n)\, \)

. . .\(\displaystyle =\, 3\,(3^n\, +\, 3^n)\, =\, 3\, (6m)\, =\, 18m\)

Which is divisible by 6. At this point I thought to myself "well, proof done!". But then I realized that 3^0 + 3^0 = 2, which is not divisible by 6. I'm assuming I made some newbie error in the induction part, so could someone point it out to me please?

The original question should have stated that n is an integer and n>0.

Your induction proof proves the statement true for integers greater than or equal to 1, because you tested it when n=1 in the first instance.

 

[syncmaster913n]

The original question should have stated that n is an integer and n>0.

Your induction proof proves the statement true for integers greater than or equal to 1, because you tested it when n=1 in the first instance.

Now I get it. (And it also explains something that wasn't obvious to me about induction in general.) Thank you!