3
$\begingroup$

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.

Answer:

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hardmath Sep 7 '13 at 13:51
  • $\begingroup$ 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. $\endgroup$ – Gil Sep 7 '13 at 13:56
  • $\begingroup$ What about using a well-ordering approach (as equivalent to induction)? The most polished proof will depend on what your class has covered. $\endgroup$ – hardmath Sep 7 '13 at 14:03
1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Gil Sep 7 '13 at 18:19

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.