Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Sometimes with series we find a solution in a form of a fraction which does not a priori obviously take only integer values. On the other hand from the sum it is pretty obvious that the sequence of partial sums can take only integer values. (arithmetic and geometric series are examples)

Someone might come along and say: Alright this is the formula for the sum. Now we need to prove that it is always an integer. Another person might say: Actually, no. We have already proved that this formula amounts to adding the series which obviously takes integer values. Who is right?

I guess my question is: after you prove $1+2+3+4+...+n= \frac{n(n+1)}{2}$ do you need to prove that the formula on the right hand side is always an integer, or does it just follow?

share|cite|improve this question
Well, exactly one of $n$ and $n + 1$ is even, so it's definitely an integer. But regardless, if you've shown that the formula holds, that implies that it only takes on integer values already. – user61527 Nov 24 '13 at 23:16
It follows because either $n$ or $n+1$ is a multiple of $2$ always when $n \neq 0$. – Sudarsan Nov 24 '13 at 23:16
If you have correctly proven that A=B then you have proved that A and B are the same thing so whatever is true about A must be true of B also, even if it isn't obvious.Some results are surprising. For example $(1+...+n)^2= (1^3+...+n^3)$ which looks like a mistake at first glance, but it'true – user254665 Oct 8 '15 at 2:10
up vote 5 down vote accepted

Perhaps a better example for the kind of question you are asking is the formula $C(n,k)=\frac{n!}{k!(n-k)!}$. It is not a-priori trivial that the RHS is an integer, but it is proven to be so if one proves that this formula counts the number of combinations of $k$ elements from $n$ elements. It is then a very rigorous proof that the RHS is indeed an integer.

share|cite|improve this answer

It follows from the identity $1 + 2 + \ldots + n = n(n + 1)/2$ that $n(n + 1)/2$ is always a natural number, since the natural numbers are closed under countable sums. But suppose we didn't have the stated identity, and wished to prove that $n(n + 1)/2$ takes on natural number values for all $n \geq 0$. We note that $n(n + 1) = n^2 + n$ and consider the cases where $n$ is odd and $n$ is even. Now the set of even numbers is closed under squaring and addition, so $n^2 + n$ is divisible by $2$ when $n$ is even, and thus $n(n + 1)/2$ is a natural number. Similarly, the odd numbers are closed under squaring, but the sum of two odd numbers is an even number. Thus, $n^2 + n$ is even when $n$ is odd, so dividing it by $2$ yields a natural number. So we see that $n(n + 1)/2$ is always a natural number.

share|cite|improve this answer

As the integers are closed under addition, it will always come out an integer. On the other hand, if you are presented with $\frac 16 n(n+1)(2n+1)$ you can prove it an integer. If you know it came from the sum of squares, there is no need to prove it.

share|cite|improve this answer

As has been stated, the fact that $n\choose 2$ is equal to a sum of integers suffices to show that it is an integer. We say that $\mathbb{Z}$ is closed under addition.

I prefer to see this by the fact that either $n$ or $n+1$ is even. I recall taking a combinatorics class and I became curious to extend this idea to a proof that $n\choose k$ is an integer. This is not quite as straightforward, but it is possible. You need to use more than just the fact that in any list of $k$ consecutive integers, one of them has to be $0\pmod{k}$.

On the other hand, consider the series of rational numbers $S_n=\sum_{k=1}^n \frac{1}{k!}$. Then $\lim_{n\rightarrow\infty}S_n=e\not\in\mathbb{Q}$, even though we have a series of rational numbers. Also, $\mathbb{R}\setminus\mathbb{Q}$ is not closed under addition, as $\pi$ and $4-\pi$ are in $\mathbb{R}\setminus\mathbb{Q}$, but their sum is not.

share|cite|improve this answer

No, you don't. You know that the sum of the series on the left side is always an integer (you can prove it by induction if you'd like), so it must follow that $\frac 12n(n+1)$ is always an integer. A similar thing occurs with $\binom{n}{m} = \dfrac{n!}{m!(n-m)!}$ with $0 \le m \le n$. You can show that $\binom{n}{m}$ is the number of ways of selecting $m$ objects out of $n$ objects where order is not important. Hence $\binom{n}{m}$ is an integer, hence $\dfrac{n!}{m!(n-m)!}$ is an integer.

In short, if you know that the left side is an integer and you have proved that it equals the right side, then you have also proved that the right side is an integer.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.