Question

Prove the following, preferably using induction so i can learn it: \[\sum_{i=1}^{n}{2i-1}=n^2\]

Answer 1

induction, step 1, prove its true for some solid value

Answer 2

provwe ir's true for n = 1 :-D

Answer 3

yep; 2(1)-1 = 1 is true

Answer 4

next step, assume its true for an arbitrary value k

Answer 5

yeah! the book also uses the letter k!

Answer 6

then show it is true for k+1

Answer 7

hmm how do i do that part?

Answer 8

\[\sum_{1}^{k}2k-1=k^2\]

Answer 9

then add 2(k+1)-1 to both sides

Answer 10

@amistre64 be careful with your notation

Answer 11

how do i prove that the statement is true for n=k?

Answer 12

will try ;)

Answer 13

you assume that k is any value; and you know its good for k=1

Answer 14

so i just assume it's good for k, and then try to prove for n=k+1?

Answer 15

yep

Answer 16

\[k^2+2k+1=(k+1)^2\]

Answer 17

if you can see a spot that it is bad for, then it a given that this wont work

Answer 18

but there is no restriction to the domain as is other than >=1

Answer 19

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

Answer 20

any questions agdgdgdwngo?
ok what does rn and dn mean in computer programming?

Answer 21

I still don't get step 2

Answer 22

assume it is true for some k?

Answer 23

proof by induction is a more rigid version of the "and so on and so forth" of days gone by

Answer 24

step 1 show it is true for first k
step 2 assume it is true for some k
step 3 use step 2 to show it is true for k+1

Answer 25

oh alright I get it... and after step 2 you basically prove the statement is true for an infinite number of cases

Answer 26

yep, because if its true for any arbitrary k, and also true for the next one after it; that covers them all

Answer 27

this type of proof can be easily done by a computer program.

Answer 28

would this program require rn and dn?

Answer 29

btw, it's a good idea to write down exactly the statement you're trying to prove, as it will make it very clear in your argument what it is you're doing.

In this problem, I would write the statement as following.

Let P(n) be the statement that
\[ \sum_{i=1}^n (2i - 1) = n^2 \]

Now. A proof by induction of this or any other such statement has two steps, as has been mentioned. Formalizing this idea, the steps are:

1. Show that P(1) is true. (Or P(m) for some other integer m)
2. Show that P(k) => P(k+1) for all \( k \geq 1 \) (Or \( k \geq m \) )

If you show these two things, then by the Principle of Mathematical Induction P(n) is true for all \( n \geq 1 \) (or \( n \geq m \) ).

Answer 30

probably not :-P never heard of rn and dn.

Answer 31

:(

Answer 32

google doesn't work

Answer 33

Now in this case, step 1 is indeed easy.

P(1) is the statement that
\[ \sum_{i=1}^1 (2i-1) = 1 \]
and this is true.

Answer 34

i know up means press u
at first i thought it meant up

Answer 35

In step 2, we start with the hypothesis P(k). And now you need to show that P(k) implies P(k+1).

The algebra for showing that has already been written down.
=========

Answer 36

that was my algebra
i can do a little algebra :)

Answer 37

hmm... I think I get it.

Answer 38

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

Answer 39

hmm alright... so first we prove P(1) by showing that 1 = 1

Answer 40

and then we prove that if P(2),...,P(k) is true, then P(k+1) is also true

Answer 41

yes

Answer 42

so alright, let's prove P(2), which is basically saying that 1 + 2 = 0.5 * 6

Answer 43

The way to write step 2 formally would be something like this:

Let us suppose P(k). I.e.,
\[ \sum_{i=1}^k (2i - 1) = k^2 \]
Now we want to show this implies P(k+1). Now
\[ \sum_{i=1}^{k+1} (2i - 1) = \sum_{i=1}^{k} (2i - 1) + \sum_{i=k+1}^{k+1} (2i - 1) \]
\[ = k^2 + \sum_{i=k+1}^{k+1} (2i - 1) \ \ \hbox{, by hypothesis P(k) } \]
\[ = k^2 + (2k + 1) \]
\[ = (k+1)^2 \]

Now as k was arbitrary, P(k) => P(k+1).

Answer 44

you only need to do it for one n=1 or n=2 but you don't need both
and then assume it is true for k
and now show it is true for k+!
\[\sum_{i=1}^{k+1}i=\sum_{i=1}^{k}i+[(k+1)] \]

Answer 45

but what does \[\sum_{i=1}^{k}i =? \]

Answer 46

it is 1 + 2 + ... + k

Answer 47

which is
what did we get to assume is true:
this right:
\[\sum_{i=1}^{k}i=\frac{k(k+1)}{2}\]
?

Answer 48

I'm confused.

Answer 49

let's just show that \[\sum_{i=1}^{k+1}i = \sum_{i=1}^{k}{i} + k + 1\]

Answer 50

or am I doing it backwards?

Answer 51

\[step \text{ 1 : } P(1)=1\]
\[step: \text{2 : } P(k)=\frac{k(k+1)}{2}\]
\[step: 3 : \text{ use step 2 \to show} \text{ (in this case:)}\]
\[ P(k+1)=P(k)+k+1=\frac{(k+1)([k+1]+1)}{2}\]

Answer 52

I think we substitute that sum of i with \[\frac{k(k+1)}{2}\] and then we show

Answer 53

So, in notation. P(n) is the statement
\[ \sum_{i=1}^n i = n(n+1)/2 \]

Now suppose P(k) i.e.,
\[ \sum_{i=1}^k i = k(k+1)/2 \]

Then
\[ \sum_{i=1}^{k+1} i =\sum_{i=1}^k i + (k+1) \]
\[ = k(k+1)/2 + (k+1), \ \ \ \hbox{ by P(k) } \]
\[ = \frac{ k^2 + k + 2k + 2}{2} \]
\[ = \frac{(k+1)(k+2)}{2} \]
I.e., P(k) => P(k+1) for arbitrary k.

Therefore, as
1. P(1) is true
2. P(k) => P(k+1) for arbitrary \( k \geq 1 \)
it follows by the PMI that P(n) is true for all \( n \geq 1 \).

Answer 54

alright I understand proof by mathematical induction!

Answer 55

first we set k to 1 and then prove P(k)

Answer 56

No.

Answer 57

no? :(

Answer 58

Go back and read my statement of the method carefully.

Answer 59

Proof by mathematical induction:
_________________________________________________________

1. Show that P(1) is true. (Or P(m) for some other integer m)
2. Show that P(k) => P(k+1) for all k≥1 (Or k≥m )

Answer 60

Yes.

Answer 61

I get it now :-D

Answer 62

Like just about everything in mathematics, you'll know you really get it when you've written out quite a few problems.

Answer 63

alright I have another problem coming up