Singing Bird Problem For my algorithms class, the professor has this question as extra credit:

The Phicitlius Bauber bird is believed to never sing the same song twice.
  Its songs are always 10 seconds in length and consist of a series of notes that are either high or low pitched and are either 1 or 2 seconds long.
  How many different songs can the Bauber bird sing?

This strikes me as a combinatorial problem, but I'm having trouble figuring out the exact formula to use to fit the included variables of 10 seconds length, 2 notes and 2 note periods.
At first, I thought that $\binom{10}{2}*\binom{10}{2}$ can be a solution, since it fits finding all combinations of both and multiplies the total.
My issue is this results in a total of 2025 possible songs, and this just seems a little on the low side.
Any assistance is appreciated. 
 A: I'm going to work under the assumption that two successive 1-second notes of the same pitch is distinct from a single 2-second note of that pitch.
Let $f(n)$ be the number of distinct $n$-second songs the bird can sing. The bird has four options for starting the song: 1-second low, 1-second high, 2-second low, and 2-second high. This gives the recursion
$$
f(n) = 2f(n-1) + 2f(n-2),
$$
with $f(0) = 1$ and $f(1) = 2$.
The associated characteristic equation is $x^2 - 2x - 2 = 0$, which has roots $x = 1 \pm \sqrt{3}$. Thus, we get the general solution
$$
f(n) = A(1 + \sqrt{3})^n + B(1 - \sqrt{3})^n.
$$
Using the initial conditions, we have the system
$$
\begin{align*}
1 &= A + B\\
2 &= A(1 + \sqrt{3}) + B(1 - \sqrt{3}),
\end{align*}
$$
which has the unique solution $A = \frac{3 + \sqrt{3}}{6}$ and $B = \frac{3 - \sqrt{3}}{6}$.
Finally, we have
$$
f(n) = \frac{3 + \sqrt{3}}{6}(1 + \sqrt{3})^n + \frac{3 - \sqrt{3}}{6}(1 - \sqrt{3})^n.
$$
For the problem at hand, we want
$$
f(10) = 18,272.
$$
A: Hint: use recursion.
You know that the first note in the Bauber bird's song is either $1$ or $2$ seconds long. In the first case, the remainder of the song is $9$ seconds long; in the second case, the remainder of the song is $8$ seconds long.
Therefore, the number of $10$-second songs equals twice (remember, the last note can be low or high) the number of $9$-second songs plus the number of $8$-second songs. Can you see how to solve the problem from here?
Also, note that it's generally a bad idea to encourage "looking for things to do with the numbers in the problem" like you said you did with your first try, $\binom{10}{2}*\binom{10}{2}$. Although formula-hunting does have its uses (esp. when doing dimensional analysis, where it's essential), if you're going to try to find a formula first, it's a good idea to check the answer for small cases (like $1$ second, $2$ seconds, etc) and then extrapolate off of that than trying to guess formulae blind.
A: Here is a non-recursive solution.
Suppose there are $a$ 1s songs and $b$ 2s songs, so $a + 2b = 10$. The total number of songs is $10 - b$.
We can count the number of such songs by first ignoring pitch and counting the ways the 1s and 2s songs can be ordered, then multiplying by $2^{a+b}$.
There are $a+1$ gaps between the $a$ 1s songs, so we want to know how many ways $b$ 2s songs can fit into $a+1$ gaps. This is $\binom{a+b}{b} = \binom{10-b}{b}$, as shown by Akash Kumar in this answer.
So we want
$$\sum_{b=0}^{5} 2^{10 - b}\dbinom{10 - b}{b} = 18,272$$
