Question

How do you do mathematical induction? simplest explanation plssss ^_^

Answer 1

at first, assume a formula holds for any natural number=k
then, from that assumption if u can prove that formula holds for n=k+1, then u can prove the formula

Answer 2

hmmm can you provide an algebraic example please? maybe i could understand better that way :DDD thanks

Answer 3

say, u have to prove: sum of first n natural numbers :n(n+1)/2
say, it holds for n=k
then sum of these terms= k(k+1)/2
now, if there are k+1 terms, then the sum= k(k+1)/2 + (k+1)= (k+1)(k+2)/2
so, proved :)

Answer 4

1º check statment is true for n=1
2º supose it's correct forn
3º using 2º prove its correct for n+1

Answer 5

yes, dont forget the first step told by myko.. i forgot to write..

Answer 6

thanks guys..ill try reviewing these and comprehend them :DDD

Answer 7

- you can getting very very nice examples and good understandably on wikipedia
- check it there again too

good luck

bye

Answer 8

some follow up question...is there a required background knowledge for this lesson? like some algebra thingies..@jhonyy9 @Arnab09 @myko ?

Answer 9

basic school algebra

Answer 10

factorize and similar

Answer 11

ohhh. thought complicated algebra thingies needed. thanks

Answer 12

Suppose you want to prove that
\[ 1 + 2 + \cdots + n \frac {n(n+1)}{2}
\]
It is true for n=1. Sine
\[ 1 = \frac {1(1+1)}{2}
\]
Suppose the fromula is true for n, let us prove it for n+1
\[ 1 + 2 + \cdots + n + n+1= \frac {n(n+1)}{2} + n+1
\]
\[ 1 + 2 + \cdots + n + n+1= \frac {n(n+1)}{2} +\frac {2( n+1)}2=\frac {(n+1)(n+2)}{2}
\]
We are done

Answer 13

There is an obvious = sign missing in the first line above

Answer 14

1+2+⋯+n = n(n+1)/2? if it is..then i think im beginning to get this...

Answer 15

Yes

Answer 16

hmm wow..i think i actually get it now...except for the last line...where did 2(n+1)/2 come from? just for LCD?

Answer 17

Yes

Answer 18

ohhh yay! i got it :DDD thanks @eliassaab <tips hat>

Answer 19

To practice try to prove that
\[ 1^2 + 2^2 + 3^2 \cdots + n^2 =\frac{1}{6} n (n+1) (2 n+1)\]

Answer 20

hmm okay..seems i underestimated that proving -__- first step would be to prove that n = something...right?

Answer 21

hmmm lez say n = 1 so..

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

yay!!!!

so now i prove for n= 1 right?

Answer 22

yes
Now suppose it is true for n and try to prove it for n+1

Answer 23

n^2 + (n+1)^2 = 1/6 n(n+1)(2n+1) + 1/6 (n+1)(n+1=1)[2(n+1) + 1]

equation right?

Answer 24

No, try again. Mimic my proof above

Answer 25

hmmm

n^2 + n+ 1 = 1/6 n(n+1)(2n+1) + n + 1?

i noticed n+1 isnt supposed to be substituted..or somethi

Answer 26

(Neglect this one :D )
I would ( was taught to) do like this
eg: 1+2+3+⋯+n = n(n+1)/2
Let p(n) be the statement 1+2+3+⋯+n = n(n+1)/2
Consider p(1)
LS= 1
RS = 1(1+1)/2 =1
So, p(1) is true
Suppose p(k) is true for some positive integers k
LS of p(k+1) = 1+2+3+⋯+k +(k+1)
= k(k+1)/2 +(k+1)
= k(k+1)/2 +2(k+1)2
= [k(k+1)+ 2(k+1)]/2
= [(k+1)(k+ 2)]/2
= (k+1)[(k+1)+1]/2
= RS of p(k+1)
therefore , p(k+1) is true
By principle of MI, p(n) is true for all positive integers n

Answer 27

hmmm it seems that was same to what elias said..i just dont get the n+1 thing @_@

Answer 28

i think i finally got the equation!!

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

yes yes? @eliassaab i just realized thatt n=1 was added a while ago due to the law of equality so i must Add (n+1)^2 too riiight?

Answer 29

n+1 was added*

Answer 30

so...

1/6 n(n+1)(2n+1) + [6(n+1)^2]/6

= (n+1)(2n^2 + n + 6n + 6]/6
= (n+1)(2n^2 + 7n + 6)/6
=(n+1)(2n+3)(n+2)/6

is this right @eliassaab ?

Answer 31

Poor presentation -0.5 mark!
Can you present the whole thing?

Answer 32

There's my answer to eliassaab 's question
Let p(n) be the statement 1^2 +2^2 +3^2 +...+n^2 = 1/6 (n)(n+1)(2n+1)
Consider p(1),
LS = 1^2 =1
RS = 1/6 (1)(1+1)(2(1)+1) = 2x3/6 =1
So, p(1) is true
Suppose p(k) is true for some positive integers k
LS of p(k+1) = 1^2 +2^2 +3^2 +...+k^2 + (k+1)^2
= (k)(k+1)(2k+1)/6 + (k+1)^2
= (k)(k+1)(2k+1)/6 + 6(k+1)^2 /6
= [(k)(k+1)(2k+1) + 6(k+1)^2 ]/ 6
= (k+1) (2k^2 +k +6k +6) /6
= (k+1) (2k^2 +7k +6) /6
= (k+1) (2k+3)(k+2) /6
= 1/6 (k+1) [ (k+2)+1][2(k+1)+1]
= RS of p(k+1)
Therefore, p(k+1) is true
By principle of MI, p(n) is true for all positive integers n

Answer 33

If I present the answer like you did, my teacher will deduct 0.5 mark for poor presentation :(

Answer 34

@lgbasallote Are you here?

Answer 35

my os lagged T_T and i cant use the equations thing..dunno how

Answer 36

dont you really understand the equation i wrote// pls save me the lag @Callisto T_T

Answer 37

Sorry, were you proving something or deriving an identity?

Answer 38

i think it was provi

Answer 39

provIng*

Answer 40

Okay, i was on the right track..

i see what you've been doing.. but i don't agree with your presentation
First, you missed a step
It is
1^2 + 2^2 +3^2 + ...+n^2 +(n+1)^2
1/6 n(n+1)(2n+1) + [6(n+1)^2]/6
= (n+1)(2n^2 + n + 6n + 6]/6
= (n+1)(2n^2 + 7n + 6)/6
=(n+1)(2n+3)(n+2)/6
You've missed the first step

Answer 41

Moreover, at first you've 'stated' they're the same, then why do you need to prove it?
1^2 = 1/6 (1)(1+1)[2(1) + 1] <-- this step ^
1 = 1/6 (2)(3)
1 = 1/6 (6)
1 = 1

You'd better separate it and say consider LS = sth
and RS = sth
and they are equal

Answer 42

you mean writing the 1^2 + 2^2 thingieS/

Answer 43

Yes you need to write it first

Answer 44

Furthermore, you need to assume that the proposition is true for some integers n before you consider n+1

Answer 45

oh at least i got the concept..yay! thanks @Callisto

Answer 46

Last but not least, you need to write
By principle of MI, the proposition is true for all positive integers n

Answer 47

what is mi??

Answer 48

mathematical induction, sorry

Answer 49

oh okay thanks

Answer 50

What I've learnt for MI are mostly proving. As for proving, personally, I think showing the whole proof clearly is very important. It's not just about getting the concept. Sorry that I've been concentrated so much on the presentation things :(

Answer 51

izfine..it's just so hard to use the equations thingy -_-

Answer 52

Better presentation (I've posted it before) :

Let p(n) be the statement 1^2 +2^2 +3^2 +...+n^2 = 1/6 (n)(n+1)(2n+1)
Consider p(1),
LS = 1^2 =1
RS = 1/6 (1)(1+1)(2(1)+1) = 2x3/6 =1
So, p(1) is true
Suppose p(k) is true for some positive integers k
LS of p(k+1) = 1^2 +2^2 +3^2 +...+k^2 + (k+1)^2
= (k)(k+1)(2k+1)/6 + (k+1)^2
= (k)(k+1)(2k+1)/6 + 6(k+1)^2 /6
= [(k)(k+1)(2k+1) + 6(k+1)^2 ]/ 6
= (k+1) (2k^2 +k +6k +6) /6
= (k+1) (2k^2 +7k +6) /6
= (k+1) (2k+3)(k+2) /6
= 1/6 (k+1) [ (k+2)+1][2(k+1)+1]
= RS of p(k+1)
Therefore, p(k+1) is true
By principle of MI, p(n) is true for all positive integers n