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

[imoO]

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]

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]

I'm still confused.......can somebody do the first one? I need to see the simliarities in steps in order to understand...

 

[tommykins]

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]

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....

 

[ashik1]

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]

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