Thread: For which natural numbers n do there exist nonnegative integers x and y such that...

For which natural numbers n do there exist nonnegative integers x and y such that... n=4x+5y? Justify your conclusion.

My conjecture/proposition:

For n=4,5,8,9,10, and 12 and beyond, there exist nonnegative integers x and y such that n=4x+5y. (0 is not a natural number)

My proof:

Let x=1, and y=0, thus 4(1)+5(0)=4 which is a natural number.
Let x=0, and y =1, thus 4(0)+5(1)=5 which is a natural number.
Let x=2, and y =0, thus 4(2)+5(0)=8 which is a natural number.
Let x=1, and y=1, thus 4(1)+5(1)=9 which is a natural number.
Let x=0, and y=2, thus 4(0)=5(2)=10 which is a natural number.

My initial step:

Assume P(12) is true. Let x=3, y=0. Thus 4(3)+5(0)=12 which is a natural number and x and y are nonnegative integers.

Inductive step:

Must prove that P(k+1)=4x+5y.

My question is, can I assume K+1=(K-3)+4 and K-3=4x+5y?

If I can then, K-3=4x+5y, then adding 4 to each side I can show that
K+1=4x+4+5y,
K+1=4(x+1)+5y since (x+1) and 5y are nonnegative integers, so are x and y.

How does this proof seem? If it isn't up to par, what am I missing?

Originally Posted by Brjakewa

Assume P(12) is true. Let x=3, y=0. Thus 4(3)+5(0)=12

You don't assume P(12); you have to prove it. Also, it helps to write explicitly what P(n) is. This helps to avoid confusion later in the proof, not to say that all symbols must be defined prior to their use.

Originally Posted by Brjakewa

Inductive step:

Must prove that P(k+1)=4x+5y.

Again, it helps to write what exactly the induction hypothesis is, which is the real question here.

Originally Posted by Brjakewa

My question is, can I assume k+1=(k-3)+4 and k-3=4x+5y?

You can assume the first equality as long as k > 3 (I am assuming that in this particular equality all operations are on natural numbers), which is true since k >= 12 by assumption. As for P(k - 3), i.e., the fact that there exist nonnegative integers x and y such that k - 3 = 4x + 5y, you cannot assume this for all k >= 12. Indeed, you have shown P(12 - 3) and P(13 - 3), but not P(14 - 3). If you leave it like this, you have a gap in the proof for P(15), P(19), P(23), etc. To cover this gap, it is sufficient to prove separately P(15), i.e., P(k + 1) when k = 14.

Suppose we are only asked to prove P(k) for k >= 12. Then one has to prove four base cases: P(12), P(13), P(14), P(15) together with the inductive step: P(k - 3) implies P(k + 1) for all k >= 15 (which is the same thing as P(k - 4) implies P(k) for all k >= 16). This way, the base case P(12) plus the inductive step will cover P(12), P(16), P(20), etc.; the base case P(13) will cover P(13), P(17), P(21), etc.; the base case P(14) will cover P(14), P(18), P(22), etc.; and finally P(15) will cover P(15), P(19), P(23), etc. Together, they cover all integers >= 12. For each number n >= 12, you can think back to the chain of numbers m such that P(m) is involved in the proof of P(n): here it is n - 4, n - 8, etc. For each of those numbers m, P(m) must be proved either in the inductive step or in the base case.

There is also a way to prove this statement by only going from P(k) to P(k + 1). Note that 4(-1) + 5 = 1, so, if 4x + 5y = k, then 4(x - 1) + 5(y + 1) = k + 1. The problem is when x = 0, i.e., 5y = k. But then y > 3 since k >= 12 and 4(4) + 5(y - 3) = k + 1.