In the first year of the Cold War, the Americans have $2$ missiles and the Russians have $14$. Every year, the Americans produce as many missiles as the Russians had the year before. On the other hand, the Russians make sure they always have twice as many as the Americans had the year before (which could mean partial demilitarization, e.g. in the second year). Find an explicit formula (i.e., depending only on $n$) describing the number of American missiles in the $n$th year of the Cold War.
As I understand the basic assumptions, it can be concluded that we have:
- $a_n = a_{n-1} + r_{n-1}$
- $a_1 = 2$
- $r_n = 2a_{n-1}$
- $r_1 = 14$
Therefore, we see that:
- $a_1 = 2$
- $r_1 = 14$
- $a_2 = 16$
- $r_2 = 4$
- $a_3 = 20$
- $r_3 = 32$
- $a_4 = 52$
- $r_4 = 40$
- $a_5 = 92$
- $r_5 = 104$
We can plug "the Russian equation" into the American one and get: $a_n = a_{n-1} + 2a_{n-2}$. From that we see that it works for $a_3, a_4, a_5$ so it is safe to assume it is correct.
$$a_n = a_{n-1} + 2a_{n-2} \iff a_n - a_{n-1} - 2a_{n-2} = 0$$
$r^2 - r - 2 = 0$
$\Delta = 9, r_1 = -1, r_2 = 2$
$a_n = a(-1)^n + b2^n$
- $a_1 = -a + 2b = 2$
- $a_2 = a + 4b = 16$
$6b = 18 \iff b = 3 \implies a + 12 = 16 \iff a = 4$
Therefore, we get:
$$a_n = 4 \cdot (-1)^n + 3 \cdot 2^n$$
Is that correct?
You correctly deduced the recurrence for the number of American missiles in the $n$th year to be:
$$ a_n = a_{n - 1} + 2 a_{n - 2} $$
with $a_1 = 2$ and $a_2 = 16$. You determined the solution to this recurrence to be:
$$ a_n = 4 (-1)^n + 3 \cdot 2^{n} $$
We verify this solution using induction:
$$ a_n = a_{n - 1} + 2a_{n - 2} $$ $$ = 4 (-1)^{n - 1} + 3 \cdot 2^{n - 1} + 2\left( 4 (-1)^{n - 2} + 3 \cdot 2^{n - 2} \right) $$ $$ = -4 (-1)^n + \frac{3}{2} \cdot 2^n + 8 (-1)^n + \frac{3}{2} \cdot 2^n $$ $$ = 4(-1)^n + 3 \cdot 2^n $$
and since the base cases hold, $a_1 = 2$ and $a_2 = 16$ we conclude the solution to the recurrence is correct.