Induction - is it alright to prove twice??

turgon

My teacher gave me a proof by induction problem today (honours), I can do it but in a wierd way.

I have to prove that [FONT=&quot]7^n[/FONT] + 2[FONT=&quot]^2n+1[/FONT] + 3 is divisible by 6. So I do the steps and I get this for n = k+1:

3[[FONT=&quot]7^k[/FONT] + 12N - 3]

where N is any number. Having done this would it be permissible to prove then that

[FONT=&quot]7^k[/FONT] + 12N - 3

is divisible by 2? So I did this and I for k = j+1 I got

2(7M-48N)

where N,M are any numbers. If i sub it back in I get that n = k+1 is

3[2(7M-48N)]
6(7M-48N)

Is it alright to do this?

P.S. 7^k is seven to the power of k.

ZorbaTehZ

You're making 2 questions out of one? (I don't know if it's acceptable even) Plus seems to me like its a lot longer than the regular way:

Prove that 7^n + 2^2n+1 + 3 is divisible by 6, ie:
7^n + 2^2n+1 + 3 = 6Z, where Z is some number.

(1)First prove for n=1
7 + 8 + 3 = 18 = 6[3] ... true

(2)Assume that it is true for n=k
7^k + 2^2k+1 + 3 = 6Z

(3)Prove for n=k+1
7^(k+1) + 2^[2(k+1)+1] + 3
7.7^k + 2^(2k+3) + 3
7[6Z - 2^2k+1 -3] + 2^(2k+3) + 3 ... from (2)
42Z - 7.2^2k+1 -21 + 2^(2k+3) + 3
42Z - 14.2^2k - 18 + 8.2^2k
42Z - 6.2^2k - 18 -> 6[7Z - 2^2k - 3] which is obviously divisible by 6.
Therefore it is true for n=k+1, if it is..... yadda-yadda.

turgon

Ill take that as an "I dont know"....!!!

turgon

Thanks for the reply, I see were I went wrong!

guX

I also have a question on induction - you're allowed to manipulate stuff algebraically before you actually prove it, right? Let's say you're asked to prove that x(n) = y(n), but you're able to manipulate x(n) using algebra (and some sequence and series stuff) so that it equals y(n), can you just do that and then do:

x(1) = y(1)
y(1) = y(1) (sub in value for x)... true
x(k) = y(k)... assume true
x(k + 1) = y(k + 1)
y(k + 1) = y(k + 1) (sub in value for x)
QED?

declan_lgs

sorry for interrupting but ftr what's the difference between x E N and x E [N with a wee zero beside it]?

This pisses me off. Book uses it sometimes and sometimes not.

N means numbers from 1,2,3... or does it include 0 too? Does N0 include 0?

dankes

Thomas_S_Hunterson

Well there's considerable debate on whether or not zero is a natural number, so, generally in the exams they'll write xEN\0 if zero is not to be included AFAIK. (the backslash symbolises "less") although it's been a year since i did the leaving so i could be wrong on the convention

And N with subscript zero is the set of natural numbers including zero AFAIK.

BMH

The set N is all the natural numbers from 0 onwards inclusive
No is N without the zero. Just remember it as "No 0" or something.

BMH

Also, a simpler way is to simply prove that the difference between f(k) and f(k+1) is divisible by six:
7^(k+1) 2^(2k+3) +3 - (7^k +2^2k+1 +3)
...
=>6(7^k +2^k) which is clearly divisible by 6.