Question

Prove by induction:

Answer 1

\[\sum_{i=1}^{n} i = n(n+1)/2\]

Answer 2

i have up to the inductive hypothesis is \[\sum_{i=1}^{k} i = k(k+1)/2 = (k^2+k)/2\]

Answer 3

What I have so far for the next part is:
\[\sum_{i=1}^{k+1} i = (k+1)(k+2)/2 = \frac{ k^2+2 }{ 2 }+\frac{ 2k+1 }{ 2 }\]

Answer 4

I'm just not entirely sure where to go from here

Answer 5

you're mostly done

Answer 6

except for a typo

Answer 7

\[\large \sum_{i=1}^{k+1} i = (k+1)(k+2)/2 = \frac{ k^2+k}{ 2 }+\frac{ 2k+2 }{ 2 } \]

Answer 8

right ?

Answer 9

\[\large \begin{align}\\ \sum_{i=1}^{k+1} i = (k+1)(k+2)/2 &= \frac{ k^2+k}{ 2 }+\frac{ 2k+2 }{ 2 } \\~\\&= \dfrac{k(k+1)}{2} + (k+1)\end{align}\]

QED

Answer 10

Okay. I looked at multiple lines when I was typing my equations. However, I did mess up the 2 for whatever reason. That helps a lot. Thank you again!

Answer 11

You could also try this directly from induction hypothesis :

\[\large \sum_{i=1}^{k} i + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1) (k+2)}{2} \]

i think thats what water is typing right now :)

Answer 12

He he he.. I was typing my next question.. :P

Answer 13

lol i have no clue wish i could attempt these .-.

Answer 14

Sometimes, I need some space for LATEX works in the question.. :P

Answer 15

So to end these kinds of problems, is it mostly a matter of getting the induction hypothesis plus something else that proves the question? I'm still kindof new at induction and trying to figure it out.

Answer 16

induction is a beautiful way of proving a statement is valid for ALL integers, its not for ending prolems :P

Answer 17

you know how/why induction proof works right ?
have u seen a proof proving induction method ?

Answer 18

In Induction, there are just three steps you have to follow to prove anything you are asked to..
Checking the validity at n = 1.
Secondly, assuming that for n = k, it is true.
Thirdly, for n = K+1, prove that it is true..

Answer 19

^^

Answer 20

I have seen them, I'm still getting used to not actually solving the problems, but proving that they can be solved. I can usually get everything up to the last ending statement as you can tell. It's just a matter of not really knowing what the right ending point is

Answer 21

Exactly ! its always a trial and error business
i like starting with "n=k" and transitioning to "n=k+1"

Answer 22

the other way is starting with "n=k+1" statement and plugging in "n=k" stuff which is okay but my personal preference is the former method

Answer 23

for example, one of my other questions proves that n^3 +2n is divisible by 3. I have the inductive hypothesis of k^3+2k and the k+1 of (k^3+2k)+3k^2+3k+3, which is divisible by 3, but I'm not really sure what I should do with the inductive hypothesis

Answer 24

to be honest i also don't know
need to try different things before arriving at something useful

Answer 25

since k^3+2k is divisible by 3,

can we write \[\large k^3 + 2k = 3t\]
for some \(t\) ?

Answer 26

k+1 step :

( `k^3+2k`)+3k^2+3k+3

here, you can replace `k^3+2k` by \(3t\) precicely because of the induction hypothesis, right ?

Answer 27

you cannot conclude "k+1" expression is divisible by 3 without using the induction hypothesis

Answer 28

That's what it looks like I may have to do. I actually found this exact question online now. That's what it is saying to do. and that does make it work out very nicely

Answer 29

Thank you again! I'm going to bed now. I have to get up soon :(

Answer 30

have good sleep :)
go thru this proof of induction method when free
http://prntscr.com/4juawh