Proof by Induction: Arithmetic Sum

[sleepingMantis]

Homework Statement

Prove for any $1 \leq m < n$ that: $$ \sum_{i = m + 1}^{n} i = \frac{(n - m)(n + m + 1)}{2} $$

Relevant Equations

$$ \sum_{1}^{n} i = \frac{n (n + 1)}{2} $$

Hi,

I am self studying induction and came across the following problem. I am stuck on how to proceed (I need to use induction, I know there is a direct proof). My proof attempt is as follows:

Let $P (m)$ be the proposition that:

$$ \sum_{i = m + 1}^{n} i = \frac{(n - m)(n + m + 1)}{2} $$

Then $P (1)$ gives:

$$ \sum_{i = 1 + 1}^{n} i = 2 + 3 + ... + n $$

Using the summation equation:

$$ \sum_{i = 2}^{n} i = \frac{n(n + 1)}{2} - 1 $$

$$ \Longleftrightarrow \sum_{i = 2}^{n} i = \frac{n^2 + n - 2}{2} $$

$$ \Longleftrightarrow \sum_{i = 2}^{n} i = \frac{(n - 1)(n + 1 + 1)}{2} $$

Therefore $P(1)$ is true.

Now assume $P(k)$ is true such that:

$$ \sum_{i = k + 1}^{n} i = \frac{(n - k)(n + k + 1)}{2} $$

Then $P(k + 1)$ gives:

$$ \sum_{i = (k + 1) + 1}^{n} i = \sum_{i = (k + 1)}^{n} i - 1 $$

Looking at the right hand side of the equality and using $P(k)$ :

$$ \frac{(n - k)(n + k + 1)}{2} - 1 $$

This simplifies down to:

$$ \frac{n^2 + n - k^2 - k - 2}{2} $$

My question is how do I proceed from here?

Are there any tricks I should be aware of to convert the numerator into the required form?

Any help is much appreciated!

 

[WWGD]

Usually you would use the assumption of P(k) to prove the result holds for P(k+1) i

n∑i=(k+1)+1i=n∑i=(k+1)i−1

Sub in the expression for P(k) on the left to the right and verify that P(k+1) holds, i.e., you get what you are supposed to get under the hypothesis, for P(k+1).

 

[Ray Vickson]

Hi,

I am self studying induction and came across the following problem. I am stuck on how to proceed (I need to use induction, I know there is a direct proof). My proof attempt is as follows:

Let $P (m)$ be the proposition that:

$$ \sum_{i = m + 1}^{n} i = \frac{(n - m)(n + m + 1)}{2} $$

Then $P (1)$ gives:

$$ \sum_{i = 1 + 1}^{n} i = 2 + 3 + ... + n $$

Using the summation equation:

$$ \sum_{i = 2}^{n} i = \frac{n(n + 1)}{2} - 1 $$

$$ \Longleftrightarrow \sum_{i = 2}^{n} i = \frac{n^2 + n - 2}{2} $$

$$ \Longleftrightarrow \sum_{i = 2}^{n} i = \frac{(n - 1)(n + 1 + 1)}{2} $$

Therefore $P(1)$ is true.

Now assume $P(k)$ is true such that:

$$ \sum_{i = k + 1}^{n} i = \frac{(n - k)(n + k + 1)}{2} $$

Then $P(k + 1)$ gives:

$$ \sum_{i = (k + 1) + 1}^{n} i = \sum_{i = (k + 1)}^{n} i - 1 $$

You said " Then $P(k + 1)$ gives:

$$ \sum_{i = (k + 1) + 1}^{n} i = \sum_{i = (k + 1)}^{n} i - 1 $$

Stop right there: that is false. You should have
$$\sum_{i=(k+1)+1}^n i = \sum_{i=k+1}^n i - \sum_{i=k+1}^{k+1} i,$$ and that last term is not equal to $-1.$

 

[sleepingMantis]

You said " Then $P(k + 1)$ gives:

$$ \sum_{i = (k + 1) + 1}^{n} i = \sum_{i = (k + 1)}^{n} i - 1 $$

Stop right there: that is false. You should have
$$\sum_{i=(k+1)+1}^n i = \sum_{i=k+1}^n i - \sum_{i=k+1}^{k+1} i,$$ and that last term is not equal to $-1.$

Thanks Ray, I see my mistake (d'oh)

I now instead have:

$$ \sum_{i = (k + 1) + 1}^{n} i = \sum_{i = (k + 1)}^{n} i - (k+1) $$

Applying the inductive assumption $P (k)$ and simplifying I get:

$$ \frac{n^2 + n - (k^2 + 3k + 2)}{2} $$

But I am not sure how to proceed from here. I thought about applying the quadratic formula to the numerator, but that gives me:

$$ n = \frac{-1 \pm \sqrt{1 + 4(k^2 + 3k + 2)}}{2} \quad (1)$$

Am I even on the right track here?

 

[Mark44]

Applying the inductive assumption $P (k)$ and simplifying I get:

$$ \frac{n^2 + n - (k^2 + 3k + 2)}{2} $$

You have $P(k) = \frac{(n - k)(n + k + 1)}{2}$. What do you expect to get for $P(k + 1)$? The numerator should be the product of two trinomials. It's not easy to factor a polynomial into the product of trinomials, but if you expand what $P(k + 1)$ should be, you will see that it is equal to what you have just above.

 

[sleepingMantis]

You have $P(k) = \frac{(n - k)(n + k + 1)}{2}$. What do you expect to get for $P(k + 1)$? The numerator should be the product of two trinomials. It's not easy to factor a polynomial into the product of trinomials, but if you expand what $P(k + 1)$ should be, you will see that it is equal to what you have just above.

Ah this is a much better approach. I was trying to factor, which I cannot seem to figure out how to do.

I guess to complete the proof:

By $P(K + 1)$ I expected:

$$ \frac {(n - (k+1))(n + (k+1) + 2)}{2} $$

Expanding and simplifying this becomes:

$$ \frac{n^2 + n - k^2 - 3k -2}{2} $$

But this is the same as:

$$ \sum_{i = (k + 1) + 1}^{n} i $$

Hence $P(k + 1)$ is also true.

 

[SammyS]

Hi,

I am self studying induction and came across the following problem. I am stuck on how to proceed (I need to use induction, I know there is a direct proof). My proof attempt is as follows:

Let $P (m)$ be the proposition that:

$$ \sum_{i = m + 1}^{n} i = \frac{(n - m)(n + m + 1)}{2} $$

Then $P (1)$ gives:
$$ \sum_{i = 1 + 1}^{n} i = 2 + 3 + ... + n $$
Using the summation equation:
$$ \sum_{i = 2}^{n} i = \frac{n(n + 1)}{2} - 1 $$ ...

Are there any tricks I should be aware of to convert the numerator into the required form?

Any help is much appreciated!

You have completed your inductive task by "counting upwards", starting with m = 1 as the Base case.

I suggest you try the induction by "counting downwards" instead. Use P(n − 1) as the base case, then show that P(k) implies P(k − 1) .

I think you may find that the algebra is less difficult. Beyond that, there is no need to use the summation equation:

$\displaystyle \sum_{i = 1}^{n} i = \frac{n(n + 1)}{2}$​

.

 

[sleepingMantis]

You have completed your inductive task by "counting upwards", starting with m = 1 as the Base case.

I suggest you try the induction by "counting downwards" instead. Use P(n − 1) as the base case, then show that P(k) implies P(k − 1) .

I think you may find that the algebra is less difficult. Beyond that, there is no need to use the summation equation:

$\displaystyle \sum_{i = 1}^{n} i = \frac{n(n + 1)}{2}$​

.

Thanks, this is a very interesting approach. I could not factor the numerator in the way I did it.

So the strategy is to use $P(n-1)$ as a base case, where $n$ can be any arbitrary value?

 

[SammyS]

Thanks, this is a very interesting approach. I could not factor the numerator in the way I did it.

So the strategy is to use $P(n-1)$ as a base case, where $n$ can be any arbitrary value?

Yes.

So P(n − 1) is the proposition that the following statement is true.

$\displaystyle \sum_{i = (n-1) + 1}^{n} { i } \ \ = \frac{(n - (n-1))(n + (n-1) + 1)}{2}$​

That's easily verified.

 

[sleepingMantis]

Yes.

So P(n − 1) is the proposition that the following statement is true.

$\displaystyle \sum_{i = (n-1) + 1}^{n} { i } \ \ = \frac{(n - (n-1))(n + (n-1) + 1)}{2}$​

That's easily verified.

Thank you that makes a lot of sense - I will try to employ this new approach as it is very handy!