Induction??? Help!!! (1 Viewer)

[wccchick]

Hey guys.

can any one give me some pointers on doing induction.

i can do the first two steps in a breeze - but the third part (prove true for n=k+1) always gets me stuck!

any tips or points to get me on the right track?

 

[Riviet]

You always need to use your assumption and substitute it into what you are required to prove. That will get you started for this step of the proof.

 

[pLuvia]

Give us an example and we'll show you while we do it. You have to be really strong in your algebraic skills in induction, you have to know where to factorise, where to move things and where not to do these things.

You should know how to manipulate the question and the assumption to suit your need

 

[insert-username]

The point where most people fall with induction is, as Riviet and pLuvia have noted, where you need to use your assumption. Basically, say you have:

Prove 1 + 2 + 4 + 8 + ... + 2^n-1 = 2ⁿ - 1 is true for all n≥1 by induction.

You know how to do the first two steps, and you end up with:

Assume true for n = k:

(1 + 2 + 4 + 8 + ... + 2^k-1) = 2^k - 1 [1]

Notice how you're saying: all the terms up to n = k is equal to 2^k - 1. Then, when you prove true for n = k + 1, you're trying to prove this:

(1 + 2 + 4 + 8 + ... + 2^k-1) + 2^(k+1)-1 = 2^(k+1) - 1 [2]

Notice the bolded and bracketed part. We've already assumed that it equals 2^k - 1 (see equation [1]). So we substitute [1] straight into [2]:

Since (1 + 2 + 4 + 8 + ... + 2^k-1) = 2^k - 1 [1]

and (1 + 2 + 4 + 8 + ... + 2^k-1) + 2^(k+1)-1 = 2^(k+1) - 1 [2]

(2^k - 1) + 2^(k+1)-1 = 2^(k+1) - 1 (subbing [1] into [2])

From there it's manipulation:

LHS = 2^k - 1 + 2^k

= 2.2^k - 1

= 2^(k+1) - 1

= RHS

Therefore, since true for n=1 and true for n = k+1 if true for n=k, it is true for n≥1 by mathematical induction.

If you practise for a while on the straightforward ones, you'll get more used to the manipulating that you need to do to complete the harder induction questions. I hope that helps out.


I_F

 

[richz]

4 steps:

eg.
1. Prove true for n=1
2. Assume True for n=k
3. Prove true for n=k+1
4. Since true for n=1 and proven true for n=k+1 therefore true for n=k+2, k+3 etc. therefore true for all n>/1

it is not always n=1 nor n=k+1, it depends on the q

 

[pLuvia]

Another example is this one

Prove that 5ⁿ+3 is divisible by 4

Step 1

Show true for n=1

S₁=8

True for n=1

Step 2

Assume n=k

S_k=5^k+3=4N [where N is an integer]

Step 3

Let n=k+1

S_k+1=5<sup>k+1[/sub]+3

This is where you have to manipulate the equations

S_k+1=5k*5+3

= (5k+3) - 12 [Using assumption]

= 4N - 12

= 4(N-3)

=4M [Where M is an integer]

Step 4

Therefore the statement is divisible by 4 by mathematical induction</sup>

 

[Riviet]

That reminds me of a couple more variations you can get:

• It's not always proving for n=1, it could be, for example, prove for all integers > 4, so you would start by proving true for n=5 (the inequality sign doesn't include 4).
• You may be asked to prove for all odd or even integers, so after proving true for your initial value, you would assume true for n=k, and depending on what your initial value was, you need to prove true for every second number ie for n=k+2. For example if you proved it true for n=1 and you need to prove for all odd integers greater than or equal to 1, the next value you need to prove is for n=1+2=3 since 3 is the next odd number, hence we have to prove for n=k+2 in this example.

• There's also the chance that you can be asked to prove something for all negative integers, so you would prove true for n=-1, so after assuming n=k, you need to prove for n=k-1 since you're subtracting by 1 for each consecutive term as in -1 to -2 to -3 etc...

 

[wccchick]

thanks heaps guys!

you've been a real help!

i'll keep you posted on how i go!

thanks again...


wccchick

 

[joesmith1975]

i got a question im stuck on.

for n=1,2,3 ....., let Sn = 1^2 + 2^2 + .... n^2

(i) Use mathematical induction to prove that, for n=1,2,3....,

Sn = 1/6 n (n+1)(2n+1)

 

[e7aine]

Show that 1^2+2^2+....+n^2 = 1/6 n(n+1)(2n+1) for n=1, 2, 3,

Testing n=1

LHS = 1
RHS = 1/6 x 1 x (1+1) x (2+1)

 

[e7aine]

whoops...pressed sumthing... newayz to continue...

Testing n = 1
LHS = 1
RHS = 1/6 x 1 x (1+1)x(2+1)
= 1

...therefore true for n=1

let n=K

1^2+2^2+...k^2 = 1/6 k (k+1)(2k+1)

show the result is true for n=k+1

1^2+2^2...k^2+(k+1)^2 = 1/6 (k+1)(k+2)(2k+3)

LHS = 1/6 k (k+1)(2k+1) + (k+1)^2
= (k+1) [1/6 k (2k+1) + (k+1)]
= 1/6 (k+1)(2k^2+7k=6)
= 1/6 (k+1)(2k+3)(k+2)
= RHS

...hope u understood what i did...

 

[joesmith1975]

yere thanks for the help!!

 

[joesmith1975]

LHS = 1/6 k (k+1)(2k+1) + (k+1)^2
= (k+1) [1/6 k (2k+1) + (k+1)]
= 1/6 (k+1)(2k^2+7k=6)
= 1/6 (k+1)(2k+3)(k+2)
= RHS

I dont know how you got from line 2 to 3

 

[SoulSearcher]

LHS = 1/6 k (k+1)(2k+1) + (k+1)^2
= (k+1) [1/6 k (2k+1) + (k+1)]
= 1/6 (k+1)(2k^2+7k=6)
= 1/6 (k+1)(2k+3)(k+2)
= RHS

simply what she did in these 2 lines was expand and simplify the major bracket

(k+1) [1/6 k (2k+1) + (k+1)]
= (k + 1) [ 1/6 2k² + k + (k + 1) ]
= (k + 1) [ { 2k² + k + 6(k + 1) } / 6)
= (k + 1) [ {2k² + 7k + 6 } / 6 ]
= 1/6 * (k + 1)(2k² + 7k + 6)

 

[joesmith1975]

yere i remember that i did this question in yr 11 and when through my notes and found it.

i took a 1/6 and (k+1) as a factor

=1/6 (k+1) [k(2k+1) +6(k+1)]
=1/6 (k+1) [k^2 +k +6k+6]
=1/6 (k+1) (2k+3)(k+2)

Thanks for help