Beginners Number Theory Problem

Printable View

Apr 7th 2009, 06:07 AM
1337h4x

Beginners Number Theory Problem

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

$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 ?
Apr 7th 2009, 08:56 AM
running-gag

Hi

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

$\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

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

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

Hint : $\sum_{j=0}^{k+1} j = \sum_{j=0}^{k} j + (k+1)$
Apr 7th 2009, 09:01 AM
1337h4x

Quote:

Originally Posted by running-gag

Hi

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

$\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

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

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

Hint : $\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.
Apr 7th 2009, 09:11 AM
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
$\sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

Then $\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)
Apr 7th 2009, 10:35 AM
1337h4x

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
$\sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

Then $\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:

$\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
Apr 7th 2009, 12:02 PM
running-gag

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:

$\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

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

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

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

Therefore $\sum_{j=0}^{k} j + (k+1) = \frac{k(k+1)}{2} + (k+1)$
Apr 7th 2009, 12:26 PM
1337h4x

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

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

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

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

Therefore $\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:

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

But I do not understand this statement:

Therefore $\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:

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

And lastly, how did this get formed exactly:

$\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.
Apr 7th 2009, 12:39 PM
running-gag

Quote:

Originally Posted by 1337h4x

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

I understand these statements:

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

But I do not understand this statement:

Therefore $\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:

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

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

From line (1) to line (2) you add (k+1)
Therefore $\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:

$\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
$\sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

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

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

Therefore $\sum_{j=0}^{k+1} j = \frac{k(k+1)}{2} + (k+1)$
May 14th 2010, 03:28 AM
1337h4x

Quote:

Originally Posted by running-gag

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

From line (1) to line (2) you add (k+1)
Therefore $\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
$\sum_{j=0}^{k} j = \frac{k(k+1)}{2}$

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

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

Therefore $\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 $\frac{k(k+1)}{2}$ . Could someone explain how we reach this point?
May 14th 2010, 07:13 AM
pollardrho06

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!
May 14th 2010, 07:44 AM
1337h4x

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