3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – drhab Dec 12 '13 at 21:05
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ no I am still having trouble, understanding the solution.. $\endgroup$ – Chris Kafita Dec 12 '13 at 21:24
  • $\begingroup$ @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$? $\endgroup$ – Brian M. Scott Dec 12 '13 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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