Induction. (1 Viewer)

[yhamam]

Hi for the past 2 lessons. ive learnt The proof of induction. And to be honest with u im always the person that is left behind....because i cant understand what the teacher is saying... can anyone explain to me how induction works please? thankz.

Well, prove true for n=1

Assume true for n=k

Prove true for n=(k+1)

Then round it up with a statement

If can't understand, look at the induction question in Maths in focus book 1

 

[ameher]

lol maths in focus so true, i was just wondering if there were any induction specific sheets or resources on bos that someone could link me to, would be appreaicated.

 

[aussiechick007]

oh my! thankyou so much! to um... soulsearcher! that explanation was all i needed lol, my maths ext exam is today and i was looking over my maths induction work and i just couldnt work out how it worked for some reason! but it all makes sense!

now hopefully it will make sense in the exam....

 

[vivid]

Key to so called 'division' induction (which by the way, is not division, its about proving something is a FACTOR) is factorisation.

Say to prove um...

(5^n)-1 is divisible by 4.

In the second step, we assume this is true for n=k, i.e.

(5^k)-1 = 4p, where p is any integer (so really this is 4 multiplied by anything)

5^k = 4p-1

Now we need to prove true for n=k+1

i.e. we are proving (5^(k+1))-1 is divisible by 4.

(5^(k+1)) = 5^k x 5^1 [basic indices rule]

Therefore, (5^(k+1))-1 = (5^k x 5)-1

We know, from the second step, that 5^k = 4p-1. So we sub it in, as with all inductions.

We get: (4p-1) x 5 - 1
= (20p-5) - 1
= 20p-4 [now we factorise!]
= 4(5p-1)
thus, it is divisible by 4, and true for n=k+1

Btw, I can't stand doing the inequalities ones if I can help it. So sorry, I'm not going to find an example of that.

 

[tommykins]

回复: Re: Induction.

Inequalities have the same concept basically, except your final statements are often from previous results or with A > B and C > D therefore A+C> B+D.

 

[thanhrox]

ok, i get the topic but i always have trouble writing out the conclusion, step 4...

therefore n=k is true.. something or other?

what do you write, generically?
- for divisible
- multiple
- inequality
- summation?


cheers.

 

[Doctor Jolly]

ok, i get the topic but i always have trouble writing out the conclusion, step 4...

therefore n=k is true.. something or other?

what do you write, generically?
- for divisible
- multiple
- inequality
- summation?


cheers.

I always write the same thing when it comes to '=' ones:

Therefore the statement is true for n=1 and n=k. It is therefore also true for n=k+1 and all values of k (depending on the question).

For divisble:

4(mumbo jumbo) which is divisble by 4.

Therefore the statement is true for n=1 and n=k. It is therefore also true for n=k+1 and all values of k (depending on the question).

For inequality:

But, 4(mumbo jumbo here) > 0, therefore, mumbo jumbo is also > 0

Therefore, the statement is true for all values of k.

 

[thanhrox]

I always write the same thing when it comes to '=' ones:

Therefore the statement is true for n=1 and n=k. It is therefore also true for n=k+1 and all values of k (depending on the question).

For divisble:

4(mumbo jumbo) which is divisble by 4.

Therefore the statement is true for n=1 and n=k. It is therefore also true for n=k+1 and all values of k (depending on the question).

For inequality:

But, 4(mumbo jumbo here) > 0, therefore, mumbo jumbo is also > 0

Therefore, the statement is true for all values of k.

oh ok, thanks. but for inquality, what do you meant by...

4(equation question thing) > 0

is it ALWAYS like that. why the 4?

 

[Doctor Jolly]

oh ok, thanks. but for inquality, what do you meant by...

4(equation question thing) > 0

is it ALWAYS like that. why the 4?

The 4 was just a random number.

I'm not too sure if it's always like that, but that's what my teacher has told me to write for inequalities. You'd be better off getting a second opinion on that one.

 

[the-derivative]

I just use the same conclusion for all types - it's really brief, but my teacher said it should suffice:

'Since the statement is true for n = k+1 and n=1, then it is true for n = 1+1 = 2, n = 2+1 = 3 ... and so on for all positive integer values of n.'

Just adjust it slightly for the different conditions you might have, for example when you do not start with n=1.

As with what Doctor_Jolly said, I don't think you need a seperate statement for inequalities.

 

[Trebla]

'Since the statement is true for n = k+1 and n=1, then it is true for n = 1+1 = 2, n = 2+1 = 3 ... and so on for all positive integer values of n.'

That conclusion is incorrect.

In Step 3 you proved the statement is true for n = k + 1 using the ASSUMPTION that n = k is true. This means that n = k + 1 is ONLY true if n = k is true. You should write:
"The statement is true for n = k + 1, if it is true for n = k"

 

[x3.eddayyeeee]

sorry to bring this thread up again.
im currently revising over notes for mathematical induction.
what does it mean by 'applications' of mathamtical induction?
help is much appreciated.

 

[x3.eddayyeeee]

i read it in the syllabus.
when i read it i was like ; "wth."
anyways. dont worry about it.

 

[light_~@~ngel]

i hate induction
cant stand it
not supposed to write mathematical essays!!!
thats for english

 

[phosphorescent]

Hurrah for induction.

But my OCDness makes it annoying ):

 

[Aerath]

i hate induction
cant stand it
not supposed to write mathematical essays!!!
thats for english

Hahahaha, don't you just go: "by process of mathematical induction etc etc"

 

[clintmyster]

Hahahaha, don't you just go: "by process of mathematical induction etc etc"

Its the one thing you do write quite a bit for just to be safe. I tend to write: "As it is true for n=1, it will hold true for n=2,3,4... and all positive integers of n by principle of mathematical induction". Not that long now was it

 

[adomad]

how would you do this one....

prove that

9^(n+2) -4^n is divisible by 5 for all n>=1

 

[The Nomad]

how would you do this one....

prove that

9^(n+2) -4^n is divisible by 5 for all n>=1

Assume true for n = k, so 9^(k+2) - 4^k = 5M, where M is a positive integer.
Prove true for n = k + 1, so prove 9^(k+3) - 4^(k+1) is divisible by 5.

9^(k+3) - 4^(k+1) = 9(9^(k+2)) - 4(4^k).

But 4^k = 9^(k+2) - 5M, by assumption.

So 9^(k+3) - 4^(k+1) = 9(9^(k+2)) - 4(9^(k+2) - 5M) = 5(5^(k+2)) + 20M = 5(5^(k+2) + 4M).

And so statement is true for n = k + 1, when assumed true for n = k.