Can I use only strong induction in order to prove $$\forall n\in\mathbb N (n\ge 6 \Rightarrow \exists a,b\in\mathbb N : n=3a+4b)$$ Is there any other option?
Alternative proof for $\forall n\in\mathbb N (n\ge 6 \Rightarrow \exists a,b\in\mathbb N : n=3a+4b)$
Asked
Active
Viewed 88 times
1
-
The title isn't supposed to replace the first line of your question. – Git Gud Nov 10 '14 at 14:49
-
1Does it work for n=9 ? – Yaitzme Nov 10 '14 at 14:51
-
Is $0\in\mathbb N$ for you? Because else the proposition is false. – AlexR Nov 10 '14 at 14:54
-
Yea, I just realized that OP is using $N$ with 0 included. Else, it doesn't even for 6 or 8 or 9. – Yaitzme Nov 10 '14 at 14:55
-
(0∈N) yea.@AlexR – Mic Nov 10 '14 at 15:07
4 Answers
2
It suffices to discuss the below three cases (below, k ∈N and 1<=k)
- $n=3k = 3*a$
- $n=3k+1 = 3*(k-1) + 4 = 3*a + 4*1$
- $n=3k+2 = 3*(k-2) + 8 = 3*(k-2) + 8 = 3*a + 4*2$
Yaitzme
- 291
-
In the cases 2,3 one needs $k-1$ respectively $k-2$ to be nonnegative. Of course that may be made clear if $n\ge 6$... [just noticed you already said $k\ge 1$] – coffeemath Nov 10 '14 at 16:41
1
if $n=3a+4b$ then $n+12k$ is also expressible in this form, so it suffices to show the proposition is true for $n \in [6,17]$
David Holden
- 18,040
1
We show that "usual" induction, i.e. going from $n$ to $n+1$, can be made to work here. Assume that $n \ge 6$ and we have a representation $n=3a+4b.$ Then either $a>0$ or not. If $a>0$ we can use one fewer $3$ and one more $4$ and arrive at $n+1.$ On the other hand if $a=0$ we have $n$ as all 4's, and there are at least two 4's involved since $n \ge 6.$ In this case we may decrease by two 4's and increase by three 3's and arrive at $n+1.$
coffeemath
- 29,884
- 2
- 31
- 52
1
More generally, if $n = pa+qb$ for positive $a, b, p, q$, then $n+2pq =p(a+q)+q(b+p) $.
Therefore, if $n$ can be represented in the form $pa+qb$ for $2pq$ consecutive values of $n$, it can be represented in that form for all larger values of $n$.
marty cohen
- 107,799