For each integer, , the Mersenne number is defined to be

Prove by induction that

So I proved it works for 1 first,

I got

so it is true for n =1

assume it s also true for n =k

so

and so with n=k+1

=

not sure what to do from here...

[tex]

Printable View

- Oct 17th 2012, 04:11 AMTweetyproof by induction help
For each integer, , the Mersenne number is defined to be

Prove by induction that

So I proved it works for 1 first,

I got

so it is true for n =1

assume it s also true for n =k

so

and so with n=k+1

=

not sure what to do from here...

[tex] - Oct 17th 2012, 04:38 AMemakarovRe: proof by induction help
You need to prove . Since you want to use the induction hypothesis, which contains , it makes sense to represent as . Then use the hypothesis.

By the way,

using the formula for the sum of geometric progression. - Oct 17th 2012, 06:28 AMTweetyRe: proof by induction help
Thank you for that, but I cant seem to follow from

I have the kth term and the k+1 therm,

and from this I need to show that this expressin is eqvialent to

But I am not sue how to 'manipulate the first expression, to get it like the second expression, - Oct 17th 2012, 06:57 AMemakarovRe: proof by induction help
No, this is not what you need to show. To begin with, there is no n. You assume the induction hypothesis for k and prove it for k + 1.

Before starting a proof by induction, you need to identify the induction statement, which is usually denoted by P(k). Usually to get the induction statement you just need to drop the universal quantifier from the statement you need to prove. In this case, you need to prove,

for all , .

Therefore, P(n) is . Just by renaming n with k (which is not required), P(k) is .

Next you prove the base case, which is P(1). (By the way, P(0) also holds. You did not write whether you need to prove P(n) for all n ≥ 0 or for all n ≥ 1.) After that, you fix an arbitrary k, assume P(k) and prove P(k + 1). So, P(k + 1) is . Start with the left-hand side, divide the sum up to k + 1 into the sum up to k plus the (k + 1)st term and use the induction hypothesis P(k) to rewrite the sum up to k.