Use induction to show that any integer greater than 3 can be represented as a sum of 2s and 5s.

Question

I know there are a few of these questions answered on other posts, but I'm still rather confused. This is my first post on here so forgive me if the formatting isn't entirely correct.

Inductive Hypothesis: $T(k) = 2a +5b$

Inductive Step: $T(k+1) = 2a +5b +1$

So I would think there would be 2 base cases.

base case 1: $4=2 * 2$ (if $b=0$)

base case 2: $5=5 * 1$ (if $b>0$)

So from looking at other posts (i.e. Proof that every number ≥ $8$ can be represented by a sum of fives and threes.) and getting some advice from a professor, it seems that this would be the way to solve it

case 1: $b=0$ & $a>2$ ($a>2$ because it has to be at least $3$, i.e. $2a+1$)

$T(k+1) = 2a + 5b + 1$

$= 2a +5b + 2 * 3 - 5$

$= 2a + 2 * 3 + 5b -5$

$= 2(a + 4) + 5(b - 1)$

Ok, so this is where I'm confused. If $b=0$, where did the $5$ come from? How can you subtract $5$ from $2 * 3$ when $5$ isn't supposed to be there in the first place? Is it because you're subtracting $5$ instead of adding it? But with that logic, you could subtract any number to get what you want....

Here's case 2.

case 2: $b>0$

$T(K+1) = 2a + 5b + 1$

$= 2a + 5b + 5 - 2 * 2$

$= 2a - 2 * 2 + 5b + 5$

$= 2(a - 2) + 5(b + 1)$

This 2nd case makes sense and it seems to be correct. So after my confusion about the 1st case, I am also wondering if these final answers (i.e. $2(a + 4) + 5(b - 1)$ and $2(a - 2) + 5(b + 1)$) are sufficient for the completion of the proof. It would seem to be sufficient because we found 2 integers $a$ & $b$ that show that $2a + 5b +1$ are the sum of $2$s and $5$s, right? Or am I way off?

Answer 1

Your set-up for the induction is not good.

First, define the claim $T(k)$ as: $k$ can be written as the sums of $2$s and $5$s. I.e.: $T(k): k = 2a + 5b$ for some $a$ and $b$

So note that with that, $T(k+1)$ becomes the claim that $k+1$ can be written as the sums of $2$s and $5$s. I.e.: $T(k+1): k+1 = 2a + 5b$ for some $a$ and $b$

... and the latter $a$ and $b$ can be (indeed have to be!) different from the former $a$ and $b$

Now, in terms of bases cases: $T(k+2)$ quickly follows from $T(k)$ (just add one more $2$), so let's exploit that. So, you do indeed need two base cases, and indeed those would be $T(4)$ and $T(5)$

And then for the step, the inductive hypothesis is that for some arbitrary $k$, $T(k)$ and $T(k+1)$ are true, and what you want to show now is that $T(k+2)$ is true - which of course trivially follows from $T(k)$: If $k=2a + 5b$, then $k+2=2(a+1)+5b$

Now, if you really want to use the standard induction scheme of going from $T(k)$ to $T(k+1)$, you can do this:

Base case: $T(4)$ holds since $4 = 2 \cdot 2$

Step: Take $k$ to be an arbitrary number $k \ge 4$

Inductive Hypothesis: Assume $T(k)$. So, $k = 2a + 5b$ for some $a$ and $b$.

Now, if $b>0$, then we can simply say that $k+1=2(a+3)+5(b-1)$

If, on the other hand, $b=0$, then we know that $k = 2a$. Since we covered the base case $4$, we know that $a \ge 2$. So, we can say that $k+1 = 2(a-2) + 5(b+1)$

Answer 2

It's easier without induction: just remark that every integer $≥6$ is of the form $4+2k$ or $5+2k$ for some natural number $k$.

To express this as an inductive argument:

Let $P(n)$ denote the statement "$n$ can be represented as desired." Then $P(4)$ and $P(5)$ are true. Suppose We have shown it up to $P(n-1)$ for some $n≥6$. Then to deduce it for $P(n)$ remark that, inductively, we know that $P(n-2)$ is true and we get a representation of $n$ by adding $2$ to a representation of $n-2$.

Answer 3

Though this is not specified, we assume that $a,b$ are non-negative.

The induction hypothesis can be written

$$n=2a+5b\land (a\ge2\lor b\ge1),$$

hence the induction step, with two cases (using $1=5-2\cdot2$ or $1=3\cdot2-5$):

$$n=2a+5b\land (a\ge2\lor b\ge1)\implies n+1=\begin{cases}a\ge 2\to2(a-2)+5(b+1)\land b+1\ge1\\b\ge 1\to2(a+3)+5(b-1)\land a+3\ge2.\end{cases}$$

For the base case:

$$4=2\cdot2+5\cdot0\land(2\ge2\lor 0\ge1).$$