# Basic induction proof that all natural numbers can be written in the form $2a + 3b$

The theorem given is:

If $n$ is a natural number then $n$ can be written in the form $2a + 3b$ for some integers $a$ and $b$.

How would I prove this by induction? I've had a go at proving this but I don't know if my technique is sound.

The base case would be when n = 1 = 2(-1) + 3(1) (if we take the natural numbers as excluding 0). Then if I assume n = 2a + 3b is true, n+1=2a+3b+1. Therefore n+1=2a+3b+2(-1)+3(1) which can be written as n+1=2(a-1)+3(b+1) which should conclude the proof.

Is this a proper proof or is there some other way of doing it? How would I prove the theorem if I took the natural numbers to include 0 (i.e. could I still use 1=2(-1)+3(1) when it would no longer be the base case)?

• Hint: 1 = 3 - 2. Your proof won't be by induction if you use this, though. – Magdiragdag Nov 12 '13 at 21:42
• @Magdiragdag, that is a most unhelpful comment. – dfeuer Nov 12 '13 at 21:43
• @dfeuer Is it? I could have commented that gcd(2,3) = 1, but considered that to be confusing for a hint. – Magdiragdag Nov 12 '13 at 21:47
• @Magdiragdag, the OP had already demonstrated that they knew what to do with that fact! – dfeuer Nov 12 '13 at 21:51

Your proof is perfectly good. You can use whatever integer $b$ you like as the base case, to prove some proposition $P(n)$ is true for all integers $n\ge b$. $0$ and $1$ are both very common base cases. You can also use induction in the other direction (e.g., for negative numbers) to prove that every integer below $b$ satisfies the proposition.
Formally, induction is usually defined in the upwards direction, and usually to start at $0$ (or $1$, depending which text you use), but extending it to do other things is quite straightforward. The downward induction can be recast as upwards: rather than induction downward in $n$, do induction upward in $-n$. Same thing.
• Of course, $n=0$ would be the "nicer" base case as you simply have $0=2\cdot 0+3\cdot 0$. :) – Hagen von Eitzen Nov 12 '13 at 22:41
Also you can avoid induction. For instance if $n$ is even then $n=2\cdot a+3\cdot 0.$ If n is odd then $n=2\cdot a+1$ for some natural $a.$ Further, $1=3-2$ so $n=2a+3-2=2\cdot (a-1)+3\cdot 1.$