1
$\begingroup$

I want to prove this statement using weak induction:

Every integer $n>11$ is a sum of two composite integers.

When I prove it I get stuck at something basic I believe but unclear for me:

I prove it separately for the odd $2n+1$ and the even $2n$ numbers:

$n$ must be: $n\ge6 (2*6>11)$

I'm stuck at the same thing for odd and even numbers so I'll ask it regarding the even ones.

I check the validity of the claim for the basic cases when $n=6$. $2*6=12=6+6$. Indeed is a sum of two composites.

Then I assume it's true for $2n$ and check for $2(n+1)$:

Then i get stuck because $2(n+1)$ and $2n$ are the of same form.

So can I assert the claim is true for $2(n+1)$ because it's the same form as $2n$ and based on my induction assumption earlier its true for $2n$?

$\endgroup$
2
  • $\begingroup$ This cannot be rigorously proved by induction. $\endgroup$ Dec 10, 2015 at 18:39
  • 1
    $\begingroup$ For $n$ even and say $\ge 8$, it is immediate, no induction, $n=4+(n-4)$ and $n-4$ is composite. If you want the two composites to be distinct, same thing works for $n\ge 10$. Now attack $n$ odd. A little more complicated, but not much. $\endgroup$ Dec 10, 2015 at 18:45

3 Answers 3

2
$\begingroup$

$2n = j + k$ ($m$ and $n$ composite)

$2(n + 1) = j + k + 2$.

If $j$ (or $k$) is even (well, if one is even they both are but I'll pretend we don't know that) then $j + 2$ (or $k + 2$) is even and thus composite. $2(n + 1) = (j + 2) + k$ (or $j + (k + 2)$); sum of composites.

If $j$ and $k$ are both odd then $j + 1$ and $k + 1$ are both even so $2(n + 1) = (j + 1) + (k + 1)$; sum of composites.

$\endgroup$
2
  • $\begingroup$ In the last line, did you mean "then $j + 1$ and $k + 1$ are both even" instead of "then $j + 1$ and $j + 1$ are both even"? $\endgroup$
    – Mr. Brooks
    Dec 10, 2015 at 22:44
  • $\begingroup$ I had to read your comment three times before I realized your two quotes weren't exactly the same. $\endgroup$
    – fleablood
    Dec 10, 2015 at 23:24
1
$\begingroup$

What you wrote makes no sense so here's a proof by induction although you don't need induction .

Start with $12=4+8$ as the base case and then assume that you wrote $$2n=4+m$$ with $m$ an even composite so $$2(n+1)=4+(m+2)$$ and $m+2$ is also an even number so it's composite .

This takes the trivial $2n=4+2(n-2)$ and turns it into an induction proof .

For the odd case you can start with the base case $13=9+4$ and keep adding a $2$ to that $4$

This is also practically equivalent with the identity : $$2n+1=9+2(n-4)$$

$\endgroup$
1
$\begingroup$

Suppose $n$ is even:

as noted by Andre Nicolas in the comments $n=(n-4)+4$ and since $n>11$ both of these are composite.

If $n$ is odd then, $n=9+(n-9)$ and both of these are composite.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .