Beginners Number Theory Problem

I just started reading about number theory and here was the first problem verbatim.

$\displaystyle SUM[j=0,n] {j} = n(n+1)/2 $

Remarks and Hints: A statement which is proved by induction often has an integral parameter,

such as n in our case. You then need to do two steps, either of which can be done first:

(1) You prove that the statement holds for the case n = 1, or whatever the first case is
that you’re interested in. This is called the base case.
(2) You prove that IF the statement holds for the case n = k, THEN it holds for the case
n = k + 1. This is called the inductive step.
Thus, for step 2, you get to ASSUME the statement for n = k, and show that this is enough
to imply it for n = k + 1. In your proof, indicate clearly when you’re doing the base case
and when you’re doing the inductive step.

So how do I prove this exactly? I know that if I sum j from 0 -> n where n=1 I'll get one, and i know for n=1 that n(n+1)/2 = 1(1+1)/2 = 1 so that makes it true, but what about for the inductive step? What do I do for n=k or n = k+1 ?

Hi

The first step consists in verifying that the statement is true for n=1

$\displaystyle \sum_{j=0}^{1} j = 1 = \frac{1.(1+1)}{2}$

For the inductive step you assume that the statement holds for the case n = k

$\displaystyle \sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

And you need to show that $\displaystyle \sum_{j=0}^{k+1} j = \frac{(k+1)(k+2)}{2}$

Hint : $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$

Quote:

---

Originally Posted by running-gag

Hi

The first step consists in verifying that the statement is true for n=1

$\displaystyle \sum_{j=0}^{1} j = 1 = \frac{1.(1+1)}{2}$

For the inductive step you assume that the statement holds for the case n = k

$\displaystyle \sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

And you need to show that $\displaystyle \sum_{j=0}^{k+1} j = \frac{(k+1)(k+2)}{2}$

Hint : $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$

---

So do I just substitute in some declared value for k and thats it? Where do I go from here? I lack the actual methodology to solve these types of problems.

(1) Suppose that you have shown the statement for n=1
(2) Suppose that you have shown that IF the statement holds for a certain value k THEN it holds for (k+1)

Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))
Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))
etc
This shows that the statement is true for every n
This is the methodology

Now let's prove the inductive step. IF the statement holds for the case n = k
$\displaystyle \sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

Then $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

Therefore the statement is true for (k+1)

Quote:

---

Originally Posted by running-gag

(1) Suppose that you have shown the statement for n=1
(2) Suppose that you have shown that IF the statement holds for a certain value k THEN it holds for (k+1)

Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))
Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))
etc
This shows that the statement is true for every n
This is the methodology

Now let's prove the inductive step. IF the statement holds for the case n = k
$\displaystyle \sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

Then $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$

Therefore the statement is true for (k+1)

---

Here you said the following:

"Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))

Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))"

But in your post before that I saw an example of n=1 and n=k, then n=k+1. I do not see what you are saying for n=2 and n=3 and how you are referencing things to statements(#). (Sorry, I am green to this course, trying to learn)

Secondly, where did this come from or how did you make this happen:

$\displaystyle \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$

I'm not up 100% on my summer operator. I'd like to understand how that worked above

Quote:

---

Originally Posted by 1337h4x

Here you said the following:

"Due to the fact that it is true for n=1 (statement (1)), then it is true for n=2 (statement (2))

Due to the fact that it is true for n=2, then it is true for n=3 (statement (2))"

But in your post before that I saw an example of n=1 and n=k, then n=k+1. I do not see what you are saying for n=2 and n=3 and how you are referencing things to statements(#). (Sorry, I am green to this course, trying to learn)

---

First you show that the statement is true for n=1.
Then you show that if it is true for a certain integer k then it is true for (k+1). The first part of this sentence is true for k=1, therefore it is true for 1+1=2 OK?
Now that it is true for k=2, it is true for 2+1=3
etc

Quote:

---

Originally Posted by 1337h4x

Secondly, where did this come from or how did you make this happen:

$\displaystyle \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$

I'm not up 100% on my summer operator. I'd like to understand how that worked above

---

$\displaystyle \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k$
$\displaystyle \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)$

Therefore $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$

Suppose that the statement is true for k
Then $\displaystyle \sum_{j=0}^{k} j= \frac{k(k+1)}{2}$

Therefore $\displaystyle \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$

Quote:

---

Originally Posted by running-gag

First you show that the statement is true for n=1.
Then you show that if it is true for a certain integer k then it is true for (k+1). The first part of this sentence is true for k=1, therefore it is true for 1+1=2 OK?
Now that it is true for k=2, it is true for 2+1=3
etc

$\displaystyle \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k$
$\displaystyle \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)$

Therefore $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$

Suppose that the statement is true for k
Then $\displaystyle \sum_{j=0}^{k} j= \frac{k(k+1)}{2}$

Therefore $\displaystyle \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$

---

Okay, I guess I need to clarify my questions a little more:

I understand these statements:

$\displaystyle \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k$
$\displaystyle \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)$

But I do not understand this statement:

Therefore $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$

How does this happen? Do you mean this is the same as:

$\displaystyle \sum_{j=0}^{k+1} j = ( \sum_{j=0}^{k} j ) + $ $\displaystyle (k+1)$

And lastly, how did this get formed exactly:

$\displaystyle \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$[/quote]

I'm curious as to if there is distribution or something with the Sum operator.

Quote:

---

Originally Posted by 1337h4x

Okay, I guess I need to clarify my questions a little more:

I understand these statements:

$\displaystyle \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k$
$\displaystyle \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)$

But I do not understand this statement:

Therefore $\displaystyle \sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$

How does this happen? Do you mean this is the same as:

$\displaystyle \sum_{j=0}^{k+1} j = ( \sum_{j=0}^{k} j ) + $ $\displaystyle (k+1)$

---

Yes that's it
(1) $\displaystyle \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k$
(2) $\displaystyle \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)$

From line (1) to line (2) you add (k+1)
Therefore $\displaystyle \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)$

Quote:

---

Originally Posted by 1337h4x

And lastly, how did this get formed exactly:

$\displaystyle \sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$

I'm curious as to if there is distribution or something with the Sum operator.

---

No
The hypothesis is that the statement is true for k
$\displaystyle \sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

We have just shown before that $\displaystyle \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)$

You substitute $\displaystyle \sum_{j=0}^{k} j$ by $\displaystyle \frac{k(k+1)}{2}$

Therefore $\displaystyle \sum_{j=0}^{k+1} j = \frac{k(k+1)}{2} + (k+1)$

Quote:

---

Originally Posted by running-gag

Yes that's it
(1) $\displaystyle \sum_{j=0}^{k} j = 1 + 2 + 3 +\cdots + k$
(2) $\displaystyle \sum_{j=0}^{k+1} j = 1 + 2 + 3 +\cdots + k + (k+1)$

From line (1) to line (2) you add (k+1)
Therefore $\displaystyle \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)$


No
The hypothesis is that the statement is true for k
$\displaystyle \sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

We have just shown before that $\displaystyle \sum_{j=0}^{k+1} j = \left(\sum_{j=0}^{k} j\right) + (k+1)$

You substitute $\displaystyle \sum_{j=0}^{k} j$ by $\displaystyle \frac{k(k+1)}{2}$

Therefore $\displaystyle \sum_{j=0}^{k+1} j = \frac{k(k+1)}{2} + (k+1)$

---

I guess I'm just struggling to understand how we come up with $\displaystyle \frac{k(k+1)}{2}$ . Could someone explain how we reach this point?

OK. Think about this... you want to add the numbers 1 to 100...

1 + 2 + ... + 100

Try adding in pairs... one pair at a time...

1 + 100 = 101

2 + 99 = 101

3 + 98 = 101

4 + 97 = 101

.

.

.

Does it ring a bell!

I see a pattern, but I don't see how it answered my question.