proof by induction in worded example

Question

I'm trying to answer the following question:

The boxes Banana Ltd. uses to ship bananas come in two sizes, one that holds three bananas and one that holds five bananas. The company promises to ship at least as many bananas as you order. Show using induction that the company can fulfil any order for nine or more bananas exactly.

The only thing I've been able to come up with is an equation: $3x + 5y = n$ where $n$ refers to the number of bananas ordered.

Also for the cases where the number of bananas ordered is less than $9$, it is obvious that the company will be able to ship at least as many bananas as ordered.

I am unsure on how to proceed from here.

EDIT:

Since the OP, I have done the following:

$3x + 5y = n$

$3x +5y + 1= n+1$

$3x+5y + 6-5 = n+1$

$3x +5y + 2*3 - 5 = n+1$

$3(x + 2) + 5(y-1) = n+1$

Therefore, if $y \ne 0$, then $x+2$ 3-capacity boxes and $y-1$ 5-capacity boxes can be used to fulfil an order of size $n+1$.

Answer 1

You’re supposed to assume that the cases are always shipped completely filled. Thus, there’s no way for the company to satisfy an order for $1,2,4$, or $7$ bananas. It can fill an order for $8$, by shipping a $3$ and a $5$, or an order for $9$, by shipping three $3$s.

HINT: Suppose that it can fill an order for $n$ bananas; i.e., there are non-negative integers $k$ and $\ell$ such that $3k+5\ell=n$.

• Can it fill an order for $n+3$ bananas?
• Wev’e seen that it can fill orders for $8$ or $9$ bananas. Can it fill an order for $10$?

If you answer those two questions correctly, you have the necessary pieces for a proof by induction. It doesn’t go from $n$ to $n+1$; it goes from $n$ to ... ? And it has more than one base case.

Further help, spoiler-protected:

Once you’ve verified that they can send $8,9$, or $10$ bananas, you can keep adding boxes of $3$ to get any larger number. If you want to be more formal about it, you can show by three inductions on $n$ that they can send $3n+2$ for any $n\ge 2$, $3n$ for any $n\ge 3$, and $3n+1$ for any $n\ge 3$. Since every integer can be written in one of these three forms, ...