# Sum of $N$ natural numbers is less than $N+2$, then each number is less than $3$.

Prove by contradiction: If the sum of $N$ natural numbers is less than $N + 2$ then each of these numbers is less than $3$.

Attempt: I have to assume that the sum of $N$ natural numbers is greater than $N+2$ then each of these numbers is greater than $3$.

What do I do now? Need help.

Cheers,

Chris

• assume that at least one of the numbers is not less than $3$ and based on that prove that the sum of the $n$ numbers cannot be less than $n+2$. It contradicts the statement that the sum is less than $n+2$. – drhab Dec 12 '13 at 21:05

You have an implication $p\to q$, where $p$ is

the sum of a certain set of $N$ natural numbers is less than $N+2$,

and $q$ is

each of the $N$ numbers is less than $3$.

To prove such an implication by contradiction, you assume that $p$ is true and $q$ is false, and you try to derive a contradiction from that assumption. Assuming that $p$ is true is assuming that you have $N$ natural numbers, say $a_1,\ldots,a_N$, whose sum is less than $N+2$. Assuming that $q$ is false is assuming that it’s not the case that each of these numbers is less than $3$, which is the same as saying that at least one of them (not all of them) is greater than or equal to $3$ (not greater than $3$).

So our assumptions are:

• $a_1,\ldots,a_N$ are natural numbers;
• $a_1+a_2+\ldots+a_N<N+2$; and
• at least one of the numbers $a_1,\ldots,a_N$ is $\ge 3$.

We can label the numbers in any order we like, so we might as well assume that $a_1\ge 3$. The other $N-1$ numbers, $a_2,\ldots,a_N$, are all at least one: $a_2\ge 1,a_3\ge 1,\ldots,a_N\ge 1$. Thus,

$$a_1+a_2+\ldots+a_N\ge 3+1+\ldots+1\;.$$

Do you see the contradiction?

• no I am still having trouble, understanding the solution.. – Chris Kafita Dec 12 '13 at 21:24
• @Chris: One of our assumptions is that $$a_1+a_2+\ldots+a_N<N+2\;,$$ so $$N+2>3+\underbrace{1+\ldots+1}_{N-1\text{ terms}}=3+(N-1)=N+2\;.$$ Is is actually possible that $N+2>N+2$? – Brian M. Scott Dec 12 '13 at 21:28