Mathematical Induction

[nik_20]

Ok, so I have a math test tomorrow, and I do not understand induction at all. Its seems easy to understand, but once I attempt the questions, I fail miserably.

Can someone give a detailed step by step view on:

a) Sums of series

b) Divisibility

c) Inequalities

I only need help on the n=k+1 bit,

Also does anyone have any helpful websites explaining them???

[dessskris]

sorry I am too late to reply!

when n=k+1, try to make the expression something in terms of the expression when n=k and k.

for sum of series, try to make the sum when n=k+1 to be something in terms of the sum when n=k and k

for divisibility, when the expression is divisible by a, let the expression when n=k become ax and then make the expression when n=k+1 to be something in terms of the expression when n=k and k

for inequalities, still, make the expression when n=k+1 to be something in terms of the expression when n=k and k but you have to be a bit creative to see the answer.

math induction questions are easy marks. you should get them right. I think it would be easier to explain if you can give question examples and then we'll try to solve them while explaining.

how did you do in the test? hope you did well anyway

[heyit'salison]

I think i'm a bit late to reply, but this is for whoever is going to read this forum later on.

Firstly you should remember that by "n = k + 1" we are looking for whether the proposition works for the next term after the end term stated in the proposition

Sum of Series:

Prove by the process of mathematical induction:

1x2x3 + 2x3x4 + 3x4x5 + ... + n(n+1)(n+2) = [n(n+1)(n+2)(n+3)]/4 where n is an element of Z⁺

let n = 1 : LHS = 6, RHS = 6

thus P₁ is true

let n = k: 1x2x3 + 2x3x4 + ... + l(k+1)(k+2) = [k(k+1)(k+2)(k+3)]/4

now test for n = k + 1:

1x2x3 + 2x3x4 + .... + k(k+1)(k+2) + (k+1)(k+2)(k+3)

remember: 1x2x3 + 2x3x4 + ... + l(k+1)(k+2) = [k(k+1)(k+2)(k+3)]/4

therefore:

[k(k+1)(k+2)(k+3)]/4 + (k+1)(k+2)(k+3)

= [k(k+1)(k+2)(k+3) + 4(k+1)(k+2)(k+3)]/4

we have a common factor of (k+1)(k+2)(k+3)

= [(k+1)(k+2)(k+3)(k+4)]/4

which is the given format. why? because if you substitute (k+1) into the RHS of n = k, you would get [(k+1)(k+2)(k+3)(k+4)]/4

therefore P_k+1 is true when P_k is true. Since P₁ is true, then P_n is true for all n element of Z⁺.

Divisibility

Prove by mathematical induction that 5²ⁿ - 1 is divisible by 24, n is an element of Z⁺

let n = 1: 5² - 1 = 24, which is divisible by 24. Therefore P₁ is true.

let n = k:

5^2k - 1 = 24A (A is any number. this is to show that no matter what k is, the answer will always be a multiple of 24)

5²ⁿ = 24A + 1

now test for n = k + 1:

5²ⁿ - 1

= 5^2k x 5² - 1

= 25(24A+1) - 1

= 600A + 25 - 1

= 600A + 24

= 24(25A+1)

then conclude with the general statement.

Inequalities

Prove by mathematical induction n² < 1 + n² for n >= 1

test for n = 1: 1 < 2

let n = k:

k < 1 + k²

now test for n = k + 1

k + 1 < 1 + (k + 1)²

k + 1 - 1 - (k + 1)² < 0

k - (k² +2k + 1) < 0

k - k² - 2k - 1 < 0

-k² - k - 1 < 0

which leads back to the general form.

then conclude with a general statement.

hope this helped (:

my life is IB!

[genepeer]

Prove by mathematical induction n² < 1 + n² for n >= 1

Talk about overkill!! Oh you meant n < 1 + n², still overkill though

[heyit'salison]

Prove by mathematical induction n² < 1 + n² for n >= 1

Talk about overkill!! Oh you meant n < 1 + n², still overkill though

oops! i'm sorry, at least you understood me