Representation of all numbers that bigger than $12$ by $3x+7y$ proof

I found an exercise in my book that requested from me to proof that all numbers that bigger than $12$ can be represented by:

$3x+7y$

They requested an induction proof,and i decided to share my answer with you,just to be sure about it.

Base Case:

we will check three base cases,$n=12,13,14$:

1.for $n=12$:

$12=3x+7y \Rightarrow x=4,y=0$

2.for $n=13$:

$13=3x+7y \Rightarrow x=2 , y=1$

3.for n=14:

$14=3x+7y \Rightarrow x=0,y=2$

we can assume that:

$n-1=3x+7y$

$∀n-1>11.$

Induction step:

We know that modulus 3 divide all the numbers to three groups of numbers:

1. $A=\{n|n≡0(\mod3)\}$
2. $B=\{n|n≡1(\mod3)\}$
3. $C=\{n|n≡2(\mod3)\}$

From the base case we can assume:

$∀a ∈ A:∃ n=3x$

$∀b ∈ B:∃ n=3x+7y$

$∀c ∈ C:∃ n=3x+14$

From that we can assume that:

1. if $n ∈ A$ and $n-1 > 11$ then $n-1 ∈ C$.

2. if $n ∈ B$ and $n-1 > 11$ then $n-1 ∈ A$.

3. if $n ∈ C$ and $n-1 > 11$ then $n-1 ∈ B$.

Is there any mistakes?

Is that a legit induction proof?

• Your approach is legitimate, to show the three base cases $n=12,13,14$ and then conclude that, by adding appropriate multiples of 3, all larger numbers can be constructed. Perhaps a more formal answer will give some pointers on arranging the argument more concisely or more clearly, but as homework it seems fine. – hardmath Sep 7 '13 at 13:51
• Thank you for the fast responding,but i have an exam next week and I need to be as much as formal as I can,I've love to see other solutions. – Gil Sep 7 '13 at 13:56
• What about using a well-ordering approach (as equivalent to induction)? The most polished proof will depend on what your class has covered. – hardmath Sep 7 '13 at 14:03

We check the correctness for $n=12$ and $n=13$: $$12=3\cdot4+7\cdot0$$ $$13=3\cdot2+7\cdot1$$ Now let's assume correctness for $n$: $$n=3x_1+7y_1$$ Now let's prove for $n+1$: $$n+1=3x_2+7y_2$$ Let's use our assumption: $$3x_1+7y_1+1=3x_2+7y_2$$ $$1=3x_2-3x_1+7y_2-7y_1/+12$$ $$13=3x_2-3x_1+7y_2-7y_1+3\cdot4$$ $$13=3(x_2-x_1+4)+7(y_2-y_1)$$ Now that's correct, as we checked: $$13=3x+7y$$

So the theorem is correct under the Induction Axiom.

This is not necessarily a proof but shows a relationship to finding the form;

$\forall{n}$ s.t. $3|n, n\ge{12}$, then $n=3x,$ for some $x\in\mathbb{N}$

$$n=3x+7\cdot0$$ $$n+1=3(x-2)+7\cdot1$$ $$n+2=3(x-4)+7\cdot2$$ Since $$n+1=3x+1=3x-6+7=3(x-2)+7\cdot1$$ and $$n+2=3x+2=3x-12+14=3(x-4)+7\cdot2$$ and of course $$n+3=3x+3=3(x+1)+7\cdot0$$

An obvious approach would be to explicitly solve this for $3x + 7y = 12 \text{ to } 18$ th

$$\begin{array}{c|ll} 3x + 7y & x & y \\ \hline 12 & 4 & 0 \\ 13 & 2 & 1 \\ 14 & 0 & 2 \\ 15 & 5 & 0 \\ 16 & 3 & 1 \\ 17 & 1 & 2 \\ 18 & 6 & 0 \end{array}$$

Now for any number $n \ge 19$ what can you say?

• Thank you for paying attention about my post,but your answer is not inductive,the point is to prove that by induction(the base case need to be proven for n=12,13,14). – Gil Sep 7 '13 at 18:19