Introduction to Induction - Confused on two areas

[imoree]

hello, i am extremely new and would like to know/ understand the following.

why when doing P(0) = P(n+1) | 2 ?
why do we divide by 2

2.
k(n-k) + k(k+1) /2 + (n-k)(n-k-1)/2 = ?

and why do we divide by 2 for the 1st problem

3. How come we come up with
2nk - 2k'2 + k'2 +k +n'2 -nk -n -nk +k'2+ k

my math is obviously way off!

thanks again

-i

 

[HallsofIvy]

hello, i am extremely new and would like to know/ understand the following.

why when doing P(0) = P(n+1) | 2 ?
why do we divide by 2

I have no idea what you mean by that. What does that "|" mean? Do you mean just "P(0)= P(n+1)/2"? That would mean that P(n)= 2P(0) for all n except 0. Or did you mean "P(n)= P(n+1)/2"? That would make a bit more sense: every number in the sequence is twice the previous one. In any case, If you are given that P(n)= P(n+1)/2, the formula itself says "divide by 2". Why it wants you to divide by 2 would depend upon where the formula came from.

2.
k(n-k) + k(k+1) /2 + (n-k)(n-k-1)/2 = ?

You need a common denominator, 2, so that is the same as 2k(n- k)/2+ (k(k+1))/2+ ((n-k)(n-k-1))/2= (2kn- 2k^2+ k^2+ k+ n^2- 2nk+ k^2+ n- k)/2
= (n^2+ n)/2
because 2kn- 2nk= 0, -2k^2+ k^2+ k^2= 0, and k- k= 0.

and why

 

[imoree]

I have no idea what you mean by that. What does that "|" mean? Do you mean just "P(0)= P(n+1)/2"? That would mean that P(n)= 2P(0) for all n except 0. Or did you mean "P(n)= P(n+1)/2"? That would make a bit more sense: every number in the sequence is twice the previous one. In any case, If you are given that P(n)= P(n+1)/2, the formula itself says "divide by 2". Why it wants you to divide by 2 would depend upon where the formula came from.



You need a common denominator, 2, so that is the same as 2k(n- k)/2+ (k(k+1))/2+ ((n-k)(n-k-1))/2= (2kn- 2k^2+ k^2+ k+ n^2- 2nk+ k^2+ n- k)/2
= (n^2+ n)/2
because 2kn- 2nk= 0, -2k^2+ k^2+ k^2= 0, and k- k= 0.

THanks HallsofIvy.. Issue is based on my lack of knowledge of math needed to understand writing algorithms for programming. I can't find a "LAYMENS TERMS" for math understanding needed so that i can test program running time vs algorithm needed.

i am still lost, but hope that i can read / practice my way to understand these terms more.

-i

 

[DrPhil]

THanks HallsofIvy.. Issue is based on my lack of knowledge of math needed to understand writing algorithms for programming. I can't find a "LAYMENS TERMS" for math understanding needed so that i can test program running time vs algorithm needed.

i am still lost, but hope that i can read / practice my way to understand these terms more.

-i

Including the image certainly helps us understand! At least the second question... Let me guess what the actual question was:

Use proof by induction to show
\(\displaystyle P(n) = 1 + 2 + 3\ + . . . +\ n = \dfrac{n (n+1)}{2}\)

Step 1: Is the statement true for n=0?
...........P(0) = 0(0+1)/2 = 0, YES

Step 2: Given P(n) true, does that guarantee P(n+1) is true?
...........P(n) = n(n+1)/2 is given
...........P(n+1) = P(n) + (n+1) = [n(n+1)/2] + (n+1)
......................= [n(n+1) + 2(n+1)]/2
......................= (n+2)(n+1)/2 = (n+1)((n+1)+1)/2 ... Q.E.D.

That completes the proof by induction. OK?