Induction (Geometric sequence)
Solution 1:
I am going to answer the following (perhaps slightly simplified) question:
Problem: Suppose that there are exactly two distinct strings of length 1 (say $a_1$ and $a_2$), and 122 distinct strings of length 2 (say $b_1,b_2,\dotsc,b_{122}$---note that I am assuming $a_ia_j \ne b_k$ for any $i,j,k$; that is, none of the original strings of length 2 is formed by concatenating strings of length 1). Let $A_n$ denote the number of strings of length $n$ that can be formed by concatenating the 124 distinct strings described above. What is $A_n$ for each $n$?
Solution: First, note that $A_1 = 2$ (as there are exactly two strings of length 1), and $A_2 = 126$ (there are 122 distinct strings of length 2, plus four strings of length 2 that are obtained by concatenating strings of length 1).
To determine $A_n$, note that there are two ways in which we can form a string of length $n$:
- We can append a string of length 1 to a string of length $n-1$. There are 2 strings of length 1, and $A_{n-1}$ strings of length $n-1$, and we are free to choose each, hence there are $2A_{n-1}$ ways of forming a string of length $n$ in this manner.
- We can append a string of length 2 to a string of length $n-2$. There are 126 strings of length 2 and $A_{n-2}$ strings of length $n-2$, and we are again free to choose each, hence there are $126A_{n-2}$ ways of forming a string of length $n$ in this manner.
Combining these, we obtain $$ A_n = 2 A_{n-1} + 126 A_{n-2},$$ which gives a formula for computing $A_n$ for any $n$.
If you require a closed form in terms of $n$, the general idea is that $A_n$ is given by $$ A_n = C_1 r_1^n + C_2 r_2^n, $$ where $C_1$ and $C_2$ are constants, and $r_1$ and $r_2$ are zeros of the characteristic polynomial (assuming that all of the zeros have multiplicity 1; this gets slightly more complicated if we allow higher order zeros). In this problem, the characteristic polynomial is given by $$ p(t) = t^2 - 2t + 126. $$ Setting this equal to zero and solving for $t$ gives us \begin{align} 0 = t^2 - 2t + 126 = (t-1)^2 + 125 &\implies (t-1)^2 = 125 \\ &\implies t-1 = \pm\sqrt{125} = \pm 5\sqrt{5} \\ &\implies t = 1 \pm 5\sqrt{5}. \end{align} Thus the closed from looks like $$ A_n = C_1 (1+5\sqrt{5})^n + C_2(1-5\sqrt{5})^n. $$ Since $A_1 = 2$ and $A_2 = 126$, we can determine $C_1$ and $C_2$ by solving the system $$ \begin{cases} 2 = C_1 (1+5\sqrt{5}) + C_2(1-5\sqrt{5}) \\ 126 = C_1 (1+5\sqrt{5})^2 + C_2(1-5\sqrt{5})^2. \end{cases} $$ This should doable by hand, but I am quite lazy---Maple suggests that the correct solution is $$ C_1 = \frac{61}{124} + \frac{63}{3100}\sqrt{5}, \qquad\text{and}\qquad C_2 = \frac{61}{124} - \frac{63}{3100}\sqrt{5}. $$ Therefore $$ A_n = \left( \frac{61}{124} + \frac{63}{3100}\sqrt{5} \right)\left( 1+5\sqrt{5} \right)^n + \left( \frac{61}{124} - \frac{63}{3100}\sqrt{5} \right)\left( 1-5\sqrt{5} \right)^n, $$ which gives a closed form formula for $A_n$ in all of its tedious glory.