There are $7$ different types of lunch dishes at the bar:
- $3$ for $1$ dollar each,
- $4$ for $2$ dollars each.
We plan to eat lunch there for the next few days, consisting of one dish every day, until we exhaust the amount of $n$ dollars ($n > 0$). How many different menus (a menu is a finite sequence of dishes, in which dishes may repeat) can we arrange for ourselves?
Write a suitable equation or system of recursive equations and give the general formula.
I calculated manually the numbers of sequences for some of the initial values of $n$:
- $a_1 = 3$ (we choose one of $1 \$ $ dishes),
- $a_2 = 4 + 3 \cdot 3 = 13$ (we choose one of $2 \$ $ dishes or twice one of $1 \$ $ dishes),
- $a_3 = 3 \cdot 4 + 4 \cdot 3 + 3 \cdot 3 \cdot 3 = 51$ (we choose one of $1 \$ $ dishes + one of $2 \$ $ dishes or we do those same choices in reverse order or we choose $3$ times one of $1 \$ $ dishes),
- $a_4 = 4 \cdot 4 + 3 \cdot 3 \cdot 4 + 3 \cdot 4 \cdot 3 + 4 \cdot 3 \cdot 3 + 3 \cdot 3 \cdot 3 \cdot 3 = 205$ (we choose one of $2 \$ $ dishes twice or we choose one of $1 \$ $ dishes twice and one of $2 \$ $ dishes, we can do that combination of choices in one of $3$ possible orders or we choose $4 $ times one of $1$ dishes).
The problem can be described as laying $1 \times n$ sidewalk with tiles of sizes:
- $1 \times 1$ for our $3$ dishes for $1$ dollar each,
- $2 \times 2$ for our $4$ dishes for $2$ dollars each.
Therefore the equation seems to be: $a_n = 3a_{n-1} + 4a_{n-2}$. It works for those $4$ initial values I have calculated manually:
- $a_1 = 3$
- $a_2 = 13$
- $a_3 = 3 \cdot 13 + 4 \cdot 3 = 39 + 12 = 51$
- $a_4 = 3 \cdot 51 + 4 \cdot 13 = 153 + 52 = 205$
To get the formula:
$\lambda^2 - 3\lambda - 4 = 0 \iff (\lambda - 4)(\lambda + 1)$
Therefore we get: $a_n = x(4)^n + y(-1)^n$ and plug values of $a_1$ and $a_2$:
- $a_1 = 3 = 4x -y \iff y = 4x - 3$
- $a_1 = 13 = 16x + y$
$13 = 16x + y$ pluging the value of $y$ implies: $13 = 16x + 4x - 3 \iff x = \frac{4}{5}$
And from that: $y = 4 \cdot \frac{4}{5} - 3 = \frac{1}{5}$
So finally: $a_n = \frac{4}{5}(4)^n + \frac{1}{5}(-1)^n$ which works fine for the first $4$ values of $a_n$:
- $a_1 = \frac{4}{5}(4) + \frac{1}{5}(-1) = \frac{16}{5} - \frac{1}{5} = \frac{15}{5} = 3$
- $a_2 = \frac{4}{5}(4)^2 + \frac{1}{5}(-1)^2 = (...) = 13$
- $a_3 = \frac{4}{5}(4)^3 + \frac{1}{5}(-1)^3 = (...) = 51$
- $a_4 = \frac{4}{5}(4)^4 + \frac{1}{5}(-1)^4 = (...) = 205$
Is my solution correct or is there something that I don't understand?