Proof by induction Watch

Narik
Badges: 13
Rep:
?
#1
Report Thread starter 9 years ago
#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
reply
sonofdot
Badges: 8
Rep:
?
#2
Report 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 1 + 3 + 3^2 + \cdots + 3^k = \frac{3^{k+1}-1}{2}

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 \frac{3^{n+1}-1}{2} but with n equalling k+1
0
reply
Narik
Badges: 13
Rep:
?
#3
Report Thread starter 9 years ago
#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 1 + 3 + 3^2 + \cdots + 3^k = \frac{3^{k+1}-1}{2}

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 \frac{3^{n+1}-1}{2} 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
reply
jj193
Badges: 14
Rep:
?
#4
Report 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
reply
sonofdot
Badges: 8
Rep:
?
#5
Report 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 2^n &lt; n! 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 n \geq 1, that..." or something
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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
    Undergraduate Open Day - Llandaff Campus Undergraduate
    Sat, 27 Apr '19

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%

Watched Threads

View All