maths induction...how??? (1 Viewer)

[becfaye2000]

Is there anyone out there that can explain 2 me how to maths induction, especially the 3 + 5+ 9 +...+ etc type. I have them in my half yearly in a few days n i'm not understanding how to do them. We did them ages ago, but... like i can remember that far back.

help would be great!!! thank u!!!

 

[kini mini]

Welcome to the forum bec

I'm not really sure where you're stuck in induction problems - is it the concept or the implementation?

The concept goes like this - if an equation holds for some number n, and also for n = k + 1 where k is some integer, then it must hold for all integers greater than n since n = k + 1 is a general result.

Reading this over it doesn't seem too satisfactory to me, if I didn't already undertsnad it I think I'd be confused too. Have you tried reading your textbook?

Post a question here and one of us will do it for you

 

[Huy]

an explanation

most of the reasoning and logic used in mathematical studies is known as deductive reasoning. for example, if fact A is given, then fact B follows.

a different kind of reasoning is known as inductive reasoning. the result is always given and it is necessary to prove that it is true. the method of proof by induction is applied to examples involve the set of natural numbers

n = {1; 2; 3; 4; ... }

a typical example might be:
show that the sum of the first n odd numbers is equal to n^2 (n a natural number)

we could test the formula be choosing the values of n at random, for example:

let n = 3, then 1 + 3 + 5 = 9 and n^2 = 3^2 = 9
so the formula is true for n = 3

similarly, we could repeat the test for several other natural numbers and show that the formula holds for each case. this, however, is not a proof -- but only establishes that the formula holds for the particular values of n which were chosen.

to prove the formula by mathematical induction, we proceed as follows:

* step 1: show that the formula is true for n = 1
* step 2: assume that the formula is true when n = k, where k is any natural number
* step 3: prove that if the formula is true for n = k, it is also true for n = k + 1
* step 4: deduce that the formula is true for any natural number (since it is true for n = 1, it is true for n = 1 + 1 = 2, and then being true for n = 2, it is true for n = 2 + 1 = 3, and so on).

n.b. the statement n = k in step 2 is often called S(k).
the statement n = k + 1 in step 3 is often called S(k) + 1

just an example to help you understand it:

* example: prove by induction that the sum of the first n odd numbers is equal to n^2, that is: 1 + 3 + 5 + 7 + 9 + ... + (2n-1) = n^2

* solution:
* step 1: test to see if statement is correct for n = 1
(2x(1) - 1) = 1^2
1 = 1^2
lhs = rhs
therefore true for n = 1

* step 2: assume the statement is true for k terms, that is, n = k.
s(k) = 1 + 3 + 5 + 7 + ... + (2k-1) = k^2

* step 3: prove the statement is true for (k+1) terms, that is, n = k + 1.
s(k+1) = [1 + 3 + 5 + 7 + ... + (2k-1)] + (2k+1)
that is ... S(k+1) = s(k) + t(k+1)

where s(k) = 1 + 3 + 5 + 7 + ... + (2k-1) = k^2 (from assumption in step 2)
and t(k+1) = (2k+1), substituting k = k+1 (adding another term for s(k + 1).

= k^2 + (2k+1)
(the RHS of our assumption in step 2) + the added term k+1

= (k+1)^2

if the statement is true for n = k, then it is also true for n = k+1 because the sum of the first (k+1) terms is equal to the perfect square (k+1)^2.

* step 4. since the statement is true for n = 1, then BY INDUCTION it must also be true for n = 1 + 1 = 2. it follows that it must also be true for n = 2 + 1, and so on. hence it must be true for all natural numbers n.

 

[becfaye2000]

tonight i read over the examples in my textbook and my formal section and anything else that might have it in it, then i tryed doing the examples and i understood the basic concept but then the example was mulitpliying things which i couldn't see y they were doing it
it just confused me

 

[becfaye2000]

reply 2 Huy

thanks for that explaination

in step 3, i'm a bit confused in the last couple of lines and how they prove that it is true for n=k+1

 

[Huy]

that would be a question asking you to prove divisibility and/or inequality statements.

there is a technique (or 'trick') in proving divisibility problems which is best illustrated by an example. you must remember this technique as the same principle applies to all proofs relating to divisibility.

* example: prove by induction that 5^n - 1 is divisible by 4 for any positive integer n.

* solution:

* step 1: test the statement for n = 1
5^1 - 1 = 4
therefore true for n = 1

* step 2: assume the expression is divisible by 4 for n = k
therefore

5^k - 1
----------- = M, where M is some integer
4

i.e. *** 5^k - 1 = 4M ***
(note, the trick is in these two lines)

* step 3: prove the expression is divisible by 4 for n = k + 1

5^k+1 - 1 = 5 x 5^k - 1 (remembering your index laws, 5 to the power of 1 times 5 to the power of k = 5^k+1)

= 5 x 5^k - 5 + 4 (since -5+4 = -1)
= 5(5^k - 1) + 4, on factorising
= 5 x 4M + 4 (using your assumption in step 2 of "5^k - 1 = 4M")
= 4(5M + 1) on factorising

which is divisible by 4 because M is an integer, from step 2.
therefore, if the statement is true for n = k, it is also true for n = k+1.

* step 4: since the statement is true for n = 1, then by induction it must also be true for n = 1 + 1 = 2. it follows, by induction, that it must also be true for n = 2 + 1 = 3, and so on. hence it must be true for all natural numbers n.

 

[Huy]

Originally posted by Huy

* step 2: assume the statement is true for k terms, that is, n = k.
s(k) = 1 + 3 + 5 + 7 + ... + (2k-1) = k^2

* step 3: prove the statement is true for (k+1) terms, that is, n = k + 1.
s(k+1) = [1 + 3 + 5 + 7 + ... + (2k-1)] + (2k+1)
that is ... S(k+1) = s(k) + t(k+1)

where s(k) = 1 + 3 + 5 + 7 + ... + (2k-1) = k^2 (from assumption in step 2)
and t(k+1) = (2k+1), substituting k = k+1 (adding another term for s(k + 1).

= k^2 + (2k+1)
(the RHS of our assumption in step 2) + the added term k+1

= (k+1)^2

okay,
in step 2, you assumed that n = k was true.
so basing step 3 on that assumption, of n = k holding true, you're proving it.

s(k+1) is equal to s(k) -- the sum to k terms, PLUS an additional term -- call it s(k+1) because the +1 is the last term.

to get the last term, you simply get the end term from S(k), and insert k+1 wherever you see k, therefore you've got:

S(k+1) = s(k) + t(k+1)

sum to k+1 terms equals sum to k terms + term (k+1)

now that you know that,
from step 2 again, your assumption
you know that LHS = RHS

instead of using the LHS which is 1 +3 + 5 + ...
you can substitute the RHS (since it holds true for n = k) instead

on expanding and factorising,
you will see that S(k+1) = (k+1)^2

which is in the same form as S(k) = k^2
but instead of k, you've got k+1
so it becomes:

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

 

[astron]

To add my 2 cents worth:

I think the clincher to getting induction correct is to understand that when doing step three, you MUST find the link between step two.

Once you assume true for n=k, you establish an equation.

When trying to prove for n=k+1
you MUST focus all your evergies on getting a link between them so that you can substitute one part into another. Once you have done that, it should be easy.

Then you finish off with a general statement, eg:

as true for n=1, then true for n=2, which follows that as true for n=2 then true for n=3, and so on for all real positive values of n.

Hope that simplifies what you have to do somewhat

 

[becfaye2000]

thanks heaps... i'm beginning 2 remember how to do this again

that means no more excuses not to study it... :-(

 

[Twintip]

Originally posted by astron
To add my 2 cents worth:

I think the clincher to getting induction correct is to understand that when doing step three, you MUST find the link between step two.

That is exactly what I was going to say. You need to get something in the test for n = k + 1 which like something in the assumption for n = k. Then you can substitute stuff in to solve it. (very techical language here lol)