0
$\begingroup$

I am trying to prove this statement, but am having some trouble with it. I think I am in the right direction but would like some feedback. Note: The proof must be completed using induction, and it looks like I need strong induction.

For every natural number n which is greater than or equal to 12, n can be written as the sum of a nonnegative multiple of 4 and a nonnegative multiple of 5.

Hint: in the inductive step, it is easiest to show that P(k − 3) → P(k + 1), where P(n) is the given proposition

So far, I have that n = 4a + 5b for some positive integer a,b. I did 4 base cases and verified that n = 12, 13, 14, 15 are true. I don't quite understand the hint. I tried a different way, and it seems to work but I'm not sure if it's right.

Base Case (n=12,13,14,15): Proven separately and fairly trivial.

Inductive Step: Suppose that the proposition is true for some n >= 12. Assume that for all natural numbers 12 <= f <= n, f = 4c + 5d for some integer c,d.

We want to show that n + 4 = 4a + 5b. Using our inductive hypothesis, we know that n <= n and thus n + 4 = (4c + 5d) + 4 = 4 (c + 1) + 5d. Since c is an integer, we know that c+1 is an integer as well and thus n + 4 = 4a + 5b (letting c+1 = a and d = b).

Since we have shown that P(n) ---> P(n+4), the proposition is true. That is, we have proven the proposition for n = 12, 16, 20,.... and n = 13, 17, 21, 25 and n = 14, 18, 22.... and n = 15, 19, 23, 27...

$\endgroup$
0
$\begingroup$

$$12+4k=(3+k)\times4$$ $$13+4k=(2+k)\times4+1\times5$$ $$14+4k=(1+k)\times4+2\times5$$ $$15+4k=k\times4+3\times5$$ Since every number $n\ge12$ can be written one of the above forms where $k\in\mathbb{N}$, we can write any number $n\ge12$ in the desired form.

$\endgroup$
0
$\begingroup$

Note that proving $P(n) \implies P(n+4)$ when $n \geq 12$ is the same thing as proving $P(k-3) \implies P(k+1)$ when $k \geq 15.$ Since you needed to include four statements of the proposition, $P(n)$ for $12 \leq n \leq 15,$ in your base case, your proof covers all the integers $n = 12$ or greater in the same way as the hint does.

The only caution I would have is that we do not usually define the natural numbers four at a time, that is, they are not axiomatically the numbers $0, 1, 2, 3$ and $n + 4$ for any $n$ that is a natural number, or $1,2,3,4$ and $n + 4$ for any $n$ that is a natural number, or anything else where the inductive part of the definition generates $n+4$ from $n.$ Instead, we get $n+1$ from $n.$

So I'm not sure exactly how your instructor would prefer to word it, but the hint suggests to me that instead of taking $P(n)$ as your proposition, where $P(n)$ means $n=4a+5b$ for non-negative integers $a,b,$ you should instead take $P'(n) = P(n)\land P(n-1) \land P(n-2) \land P(n-3)$ as your proposition, with base case $n=15.$ Then in order to prove that $P'(k) \implies P'(k+1),$ you use the fact that $P(k - 3) \implies P(k+1)$ and the fact that each of the other three sub-propositions implies itself.

On the other hand, if a statement $P(n)$ is true for some set of $m$ consecutive integers $n_0, n_0 + 1, \ldots, n_0 + m - 1,$ and if $P(n) \implies P(n+m),$ then $P(n)$ is true for all integers $n$ such that $n \geq n_0.$ Given this general fact about inductive proofs, your proof shows what it was desired to show.

$\endgroup$
1
  • $\begingroup$ See also ths answer for another view of such inductions. $\endgroup$ May 6 '19 at 2:36

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.