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)?

Thanks for your help.

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

  • $\begingroup$ Thanks! What you said about using induction in the other direction is really interesting and helpful; I hadn't thought about doing that. $\endgroup$ – FalseAzure Nov 12 '13 at 21:45
  • $\begingroup$ @FalseAzure, the integers are very nice: you can split them at the point of your choice to get one set that looks a lot like the natural numbers and one set that looks a lot like the natural numbers turned around backwards. In (most?) more general inductive contexts (structural induction, transfinite induction, and wellfounded induction), only the upwards way makes sense. $\endgroup$ – dfeuer Nov 12 '13 at 21:49
  • 1
    $\begingroup$ Of course, $n=0$ would be the "nicer" base case as you simply have $0=2\cdot 0+3\cdot 0$. :) $\endgroup$ – 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.$


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.