# Proof by inductionWatch

#1
I've just started this topic and I need help showing how you would work out a question like this, as my textbook totally jumps the gun and doesn't explain it very well.

Use induction to prove the following for all natural numbers 'n'.

1 + 3 + 3^2 + 3^3 + ... + 3^n = [1/2][3^(n+1) - 1]

I would really appreciate it if someone could do this step by step! Thanks!
0
9 years ago
#2
A proof by induction is in two parts: you prove that it is true in a base case, then you prove that if it true for some k, then it must be true for k+1.

The base case first - does the formula work when n=0?

Then assume it is true for n=k, ie you assume that

Can you see how you can get from this to showing it is true for n=k+1?

Spoiler:
Show
Add the next term, 3^(k+1) to both sides of the equation, then rearrange the rhs to get it in the form you need, which is but with n equalling k+1
0
#3
(Original post by sonofdot)
A proof by induction is in two parts: you prove that it is true in a base case, then you prove that if it true for some k, then it must be true for k+1.

The base case first - does the formula work when n=0?

Then assume it is true for n=k, ie you assume that

Can you see how you can get from this to showing it is true for n=k+1?

Spoiler:
Show
Add the next term, 3^(k+1) to both sides of the equation, then rearrange the rhs to get it in the form you need, which is but with n equalling k+1
Wow thanks! That really helped! I just want to ask whether you always use n=0, when n is a natural number [unless stated otherwise] or does it really matter? Thanks again!
0
9 years ago
#4
So.
Sum of 3^r
from r = 0 to n
is equal to [1/2][3^(n+1) -1]

Basis Case: n=0
3^0 = 1
1/2[3-1] = 1
True
Assume true for all n=k (substitute k in for n)
Wish to proove true for all n=k+1 (substitute (k+1) in for n):
1/2[3^(k+2)-1] = 1/2[3^(k+1)] + 3^(k+1) <-- You can see the LHS is standard. But the RHS is the sum of n=k plus 3^(k+1) which is what we do, since we have assumed n=k is true.
Expanding brackets (only way)
1/2*3^(k+2) - 1/2 = 1/2*3^(k+1) - 1/2 + 3^(k+1)
-1/2 cancels:
1/2*3^(k+2) = 3/2*3^(k+1)
Since 3*3^(k+1) = 3^(k+2) we have prooved it true for n=k+1, (assuming n=k)
This is enough since it is true for n=0, must be true for n=k+1 e.g. n=1 and in turn n=2 etc..
even though we never prooved the actual n=k.
0
9 years ago
#5
(Original post by Narik)
Wow thanks! That really helped! I just want to ask whether you always use n=0, when n is a natural number [unless stated otherwise] or does it really matter? Thanks again!
For the base case, you use whatever integer is appropriate. In your case, this was 0, since the first term in the sum was 3^0. Normally, its more likely to be 1, for example if you were proving that 1+2+3+...n = 0.5n(n+1) by induction, the first term is when n=1. There are also times when it is other numbers, for example you can prove that by induction, but this is only true for n greater than or equal to 4, so here the base case would be n=4.

The question should usually make it clear what the base case should be, by starting "Prove, for , that..." or something
0
X

new posts
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Cranfield University
Cranfield Forensic MSc Programme Open Day Postgraduate
Thu, 25 Apr '19
• University of the Arts London
Open day: MA Footwear and MA Fashion Artefact Postgraduate
Thu, 25 Apr '19
• Cardiff Metropolitan University
Sat, 27 Apr '19

### Poll

Join the discussion

#### Have you registered to vote?

Yes! (179)
39.43%
No - but I will (25)
5.51%
No - I don't want to (32)
7.05%
No - I can't vote (<18, not in UK, etc) (218)
48.02%