• Best of luck to the class of 2024 for their HSC exams. You got this!
    Let us know your thoughts on the HSC exams here
  • YOU can help the next generation of students in the community!
    Share your trial papers and notes on our Notes & Resources page
MedVision ad

Mathematical Induction....completely lost... (1 Viewer)

imoO

Member
Joined
Apr 6, 2008
Messages
302
Gender
Male
HSC
2009
Okay so I've just started this...and I have no idea what the hell I am doing.

1+3+5+...+(2n-1) = n^2

I understand the n=1 bit...I just have to test that on LHS and RHS..but as soon as I see n=k...I'm confused...and then somehow I used n=k+1 after that? Can somebody please explain!!!

If you could also show me this one so I can understand what youy are doing in more depth that would be great. I have a whole exercise to do by tomorrow and I'm not too sure I can get it done...

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

Thank you all so much!!
 

namburger

Noob Member
Joined
Apr 29, 2007
Messages
228
Gender
Male
HSC
2008
imoO said:
Okay so I've just started this...and I have no idea what the hell I am doing.

1+3+5+...+(2n-1) = n^2

I understand the n=1 bit...I just have to test that on LHS and RHS..but as soon as I see n=k...I'm confused...and then somehow I used n=k+1 after that? Can somebody please explain!!!

If you could also show me this one so I can understand what youy are doing in more depth that would be great. I have a whole exercise to do by tomorrow and I'm not too sure I can get it done...

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

Thank you all so much!!
The n=1 part is simple
For the n=k part, you are ASSUMING it is true.

From your example:
ASSUME that it is true for n = k
1+3+3^2+...+3^(k-1) = 1/2(3^k - 1)

When n = k + 1
You must prove that 1+3+3^2+...+3^(k-1) + 3^(k) = 1/2(3^(k+1) - 1)

As you can see, the pattern is adding 3 to the power of 0,1,2,3,4 until n-1 times SO when n =k + 1, you must add 3^k to both sides of your assumption

1+3+3^2+...+3^(k-1)+ 3^k = 1/2(3^k - 1) + 3^k
= [(3^k - 1) + 2.3^k]/2
= [3.3^k - 1]/2
= 1/2(3^(k+1) - 1)

Hence it is true. There are like 4 types of induction questions. practice and you will understand
 

imoO

Member
Joined
Apr 6, 2008
Messages
302
Gender
Male
HSC
2009
I'm still confused.......can somebody do the first one? I need to see the simliarities in steps in order to understand...
 

tommykins

i am number -e^i*pi
Joined
Feb 18, 2007
Messages
5,730
Gender
Male
HSC
2008
1+3+5+...+(2n-1) = n^2

n = 1.

2n -1 = n^2

2-1 = 1 true for n =1

Assume true for n = k.

just replace n's with k's here

1+3+5+...+(2k-1) = k^2

now, prove true for n = k+1

on the LHS, you add the "k+1" term.

1+3+5+...+(2k-1)+(2k+1) = (k+1)^2 -> RHS is our expected result.

By considering 1+3+5+...+(2k-1) = k^2

we sub in k^2 into the part i bolded.

thus k^2 + 2k + 1 = (k+1)^2

expand the RHS , itbecomes equal to LHS. You then write a statement.

If statement true for n = k then it is true for n = k+1, but since it is true for n = 1, by mathematical induction it is true for all n>1
 

Trebla

Administrator
Administrator
Joined
Feb 16, 2005
Messages
8,380
Gender
Male
HSC
2006
You have 3-4 steps in an induction proof

Using 1+3+5+...+(2n-1) = n² as an example:

Step 1: Test the initial case (so for this example that is n = 1)
LHS = 1
RHS = 1² = 1
LHS = RHS hence statement is true for n = 1

All we have done here is verify the statement is correct for one particular value of n (here it is n = 1). We haven't proved it is correct for any other value of n yet.

Step 2: ASSUME the statement is true for n = k
1+3+5+...+(2k-1) = k²

Now we "pretend" the statement is correct for some random value of n. Note that we haven't proved it is correct, we've just pretended it is

Step 3: Prove the statement is true for the NEXT value of n (in this case n = k+1)
Required to prove statement is true for n = k + 1
1+3+5+...+(2k+1) = (k+1)²

LHS = 1+3+5+...+ (2k+1)
if we just peek at the second last term:
= 1+3+5+...+ (2k-1) + (2k+1)
= [1+3+5+...+ (2k-1)] + (2k+1)
What does the stuff in the brackets look like? Our ASSUMPTION from step 2!
= k² + 2k + 1
= (k + 1)²
= RHS

***IF the statement it true for n = k then the statement is true for n = k + 1

Now, IF our assumption is correct for n = k, then it is correct for n = k + 1 since we used it to prove. If our assumption is wrong for n = k, then n = k + 1 must also be wrong. But how do we know if the statement is correct or not? All we've done is pretend it was correct but we don't know for sure if it actually is correct. The key lies in looking at Step 1!

Step 4: Conclusion
Since the statement is true for n = 1 (from Step 1), then it is true for n = 1 + 1 = 2. If it is true for n = 2, then it is true for n = 2 + 1 = 3 and so on. Hence by induction the statement is true for all n integers greater than or equal to 1.

If we look at step 1, we KNOW the statement is DEFINITELY true for n = 1 as proven without having to pretend it is true. So it is true for one value of n. Now from step 3***, we said that IF it is true for one value then it is true for the next. So if n = k = 1 is true then it is also true for n = k + 1 = 1 + 1 = 2. So it is DEFINITELY TRUE for 2. Now if we make n = k = 2 this time which we know is now true, then n = k + 1 = 2 + 1 = 3 is also true. Following the inductive pattern since n = 3 is true then n = 4 is true. Since n = 4 is true then n = 5 is true and so on....
 
Last edited:

ashik1

New Member
Joined
Apr 8, 2008
Messages
22
Gender
Male
HSC
2008
Trebla said:
You have 3-4 steps in an induction proof

Using 1+3+5+...+(2n-1) = n² as an example:

Step 1: Test the initial case (so for this example that is n = 1)
LHS = 1
RHS = 1² = 1
LHS = RHS hence statement is true for n = 1

All we have done here is verify the statement is correct for one particular value of n (here it is n = 1). We haven't proved it is correct for any other value of n yet.

Step 2: ASSUME the statement is true for n = k
1+3+5+...+(2k-1) = k²

Now we "pretend" the statement is correct for some random value of n. Note that we haven't proved it is correct, we've just pretended it is

Step 3: Prove the statement is true for the NEXT value of n (in this case n = k+1)
Required to prove statement is true for n = k + 1
1+3+5+...+(2k+1) = (k+1)²

LHS = 1+3+5+...+ (2k+1)
if we just peek at the second last term:
= 1+3+5+...+ (2k-1) + (2k+1)
= [1+3+5+...+ (2k-1)] + (2k+1)
What does the stuff in the brackets look like? Our ASSUMPTION from step 2!
= k² + 2k + 1
= (k + 1)²
= RHS

***IF the statement it true for n = k then the statement is true for n = k + 1

Now, IF our assumption is correct for n = k, then it is correct for n = k + 1 since we used it to prove. If our assumption is wrong for n = k, then n = k + 1 must also be wrong. But how do we know if the statement is correct or not? All we've done is pretend it was correct but we don't know for sure if it actually is correct. The key lies in looking at Step 1!

Step 4: Conclusion
Since the statement is true for n = 1 (from Step 1), then it is true for n = 1 + 1 = 2. If it is true for n = 2, then it is true for n = 2 + 1 = 3 and so on. Hence by induction the statement is true for all n integers greater than or equal to 1.

If we look at step 1, we KNOW the statement is DEFINITELY true for n = 1 as proven without having to pretend it is true. So it is true for one value of n. Now from step 3***, we said that IF it is true for one value then it is true for the next. So if n = k = 1 is true then it is also true for n = k + 1 = 1 + 1 = 2. So it is DEFINITELY TRUE for 2. Now if we make n = k = 2 this time which we know is now true, then n = k + 1 = 2 + 1 = 3 is also true. Following the inductive pattern since n = 3 is true then n = 4 is true. Since n = 4 is true then n = 5 is true and so on....
lol, nice usage of the word pretend:)
 

ashik1

New Member
Joined
Apr 8, 2008
Messages
22
Gender
Male
HSC
2008
imoO said:
Okay so I've just started this...and I have no idea what the hell I am doing.

1+3+5+...+(2n-1) = n^2

I understand the n=1 bit...I just have to test that on LHS and RHS..but as soon as I see n=k...I'm confused...and then somehow I used n=k+1 after that? Can somebody please explain!!!

If you could also show me this one so I can understand what youy are doing in more depth that would be great. I have a whole exercise to do by tomorrow and I'm not too sure I can get it done...

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

Thank you all so much!!
Dude r u seriously considering doing 4u maths, far, good luck but u need practice and dont take rubbish advice from ppl, the understanding will come naturally for maths induction as it's probably the easiest parts juxtaposing with equations
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top