Mathematical Induction Year 12 math question

Question

Prove by mathematical induction that $n$ can be written as an expression of multiples of $4$ and $5$, $n\geq12$

I understand the initial case where $n = 12$ $$ 12 = 4\cdot 3 + 5\cdot 0 $$ which is a multiple of $4$ and $5$

Assumption: let $n = k$ so $$ k = 4x + 5y $$ Rearranging the equation you get: $4x = k - 5y$

Prove for $n = k+1$

RTP: $k+1 = 4(x-1) + 5(y+1)$ BUT you can also have the fact of: $k+1 = 4(x+4)$ - because it can go back to being a string of $4$s

Is this the right track?? then you look at the RHS of both cases

Answer 1

HINT:

Induction is used to prove statements about infinitely many things.

For induction, you need $3$ steps.

1) Check if the statement you are about to prove is true for some small values of $n$

2) Assume that the statement is true for some value of $n$ say $k$

3) USING 2) prove that the statement is true for $k+1$.

One usually says the analogy of dominoes. Imagine an infinitely long chain of dominoes standing in a row. You would like to show that "all of them will fall". To do so you show that whenever one falls it will tilt the next one (this is the essence of step 3). And you show that the first (or one in the beginning will fall) this is the essence of step 1).

1) check for some small values of $n$ say $n=13$, in this case

$$ 2\cdot 4+1\cdot 5 =13 $$

Nice!

2) assume that the statement is true for some $n=k$ where $k\ge 14$ so you say that you are sure that the equation $$ k= a\cdot 4+b\cdot 5 $$ has integer solutions for $a$ and $b$

I leave the rest for you

Hope this helped

---

EDIT after some comments and edit in the question

Nice! You are on the right track!

Actually nothing in the question says that your $x$ and $y$ has to be positive so you are basically done!

Answer 2

This is my solution for your question

So we have

$12=4\times 3$,

$13=4\times 2 +5$,

$14=4 + 5\times 2$,

$15=5 \times 3$,

$16= 4 \times 4$.

You can see that if we have a 4 and we want to increase by 1 then we change one 1 by one 5. And if we don't have one 4, then by induction from 15, we must have at least $3\times 5$, so we swap 3 number 5s for 4 number 4s. So $4\times 4 - 5\times 3 =1$

Q.E.D

Answer 3

You have assumed that $k=4x+5y$ and we want to show that $k+1 = 4m+5n$

We can say that \begin{align}k+1&=(4x+5y)+1\\ &=(4x+5y)+(5-4)\\ &=4(x-1)+5(y+1)\end{align}

so now we can say that $m=x-1$ and $n=y+1$ which are both integers and we have proved the inductive step

Answer 4

Base case:

$$12=4\cdot 3+5\cdot0$$

Inductive steps:

• if $n$ is a linear combination of $4$ and $5$, so is $n+5$ (obvious);
• if $n$ is a linear combination of $4$ and $5$, so is $n+4$ (obvious);
• if $n$ is a linear combination of $4$ and $5$, so is $n+3$ (because $3=5\cdot3-4\cdot3$);
• if $n$ is a linear combination of $4$ and $5$, so is $n+2$ (because $2=5\cdot2-4\cdot2$);
• if $n$ is a linear combination of $4$ and $5$, so is $n+1$ (because $1=5-4$).

Hence if true for $n$, then true for $n,n+1,\cdots n+5,n+5+1,n+5+2,\cdots n+5+5,\cdots$ and finally true for all $n\ge 12$.

Note: as we never deduct multiples of $4$ with a coefficient higher than $3$, the coefficients are guaranteed to remain non-negative. This condition was left implicit in the inductive steps, for brevity.