Recurrence Relations Questions and Answers

Answer: B

The recurrence is \(a_{n} = a_{n-1} + a_{n-2}\).

Split the valid \(n\)-bit strings by their last bit. If it ends in 0, the first \(n-1\) bits can be any valid string: \(a_{n-1}\) ways. If it ends in 1, the bit before must be 0 (no two consecutive 1s), and the first \(n-2\) bits can be any valid string: \(a_{n-2}\) ways. Adding the cases gives the Fibonacci recurrence.

Check with small cases: \(a_{1} = 2\) (0, 1), \(a_{2} = 3\) (00, 01, 10), and \(a_{3} = 5\) = 3 + 2. The other recurrences overcount; for example \(a_{n-1} + 2a_{n-2}\) gives 7 for \(n = 3\).

Answer: A

The true statement is \(T(n) = \Theta(2^{n})\).

The characteristic equation of \(T(n) = 5T(n-1) - 6T(n-2)\) is \(r^{2} - 5r + 6 = 0\), with roots 2 and 3, so \(T(n) = a2^{n} + b3^{n}\). The initial values fix the constants:

\[ \begin{aligned} T(0) &= a + b = 1 \\ T(1) &= 2a + 3b = 2 \\ \Rightarrow b &= 0, \quad a = 1 \end{aligned} \]

So \(T(n) = 2^{n}\) exactly (check: \(T(2) = 10 - 6 = 4\)). The \(3^{n}\) term would normally dominate, which is the trap, but these initial conditions make its coefficient zero. The \(n2^{n}\) and \(n3^{n}\) forms arise only from a repeated root, which this equation does not have.

Answer: D

The generating function is \(\frac{3-x}{(1-x)^{2}}\).

Split the sequence into its two parts and use the standard series \(\sum x^{n} = \frac{1}{1-x}\) and \(\sum n x^{n} = \frac{x}{(1-x)^{2}}\):

\[ \begin{aligned} \sum (2n + 3)x^{n} &= \frac{2x}{(1-x)^{2}} + \frac{3}{1-x} \\ &= \frac{2x + 3(1-x)}{(1-x)^{2}} = \frac{3-x}{(1-x)^{2}} \end{aligned} \]

Check: the expansion starts \(3 + 5x + 7x^{2}\), matching \(a_{0} = 3\), \(a_{1} = 5\). \(\frac{3}{(1-x)^{2}}\) starts 3 + 6x, \(\frac{3x}{(1-x)^{2}}\) starts with 0, and \(\frac{2-x}{(1-x)^{2}}\) starts with 2, so none of them fits.

Answer: A

The closed form is \(\frac{x(1 + x^{2})}{(1 - x^{2})^{2}} + \frac{1}{1 - x}\).

Write \(a_{n} = 1 + b_{n}\), where \(b_{n} = n\) for odd \(n\) and 0 otherwise. The constant part gives \(\sum x^{n} = \frac{1}{1-x}\). For the odd part, start from \(g(x) = \sum n x^{n} = \frac{x}{(1-x)^{2}}\) and keep only the odd powers with \(\frac{g(x) - g(-x)}{2}\):

\[ \begin{aligned} \sum_{n \text{ odd}} n x^{n} &= \frac{1}{2}\left[\frac{x}{(1-x)^{2}} + \frac{x}{(1+x)^{2}}\right] \\ &= \frac{x\left[(1+x)^{2} + (1-x)^{2}\right]}{2(1-x^{2})^{2}} \\ &= \frac{x(1 + x^{2})}{(1 - x^{2})^{2}} \end{aligned} \]

Check the first terms: the sequence is 1, 2, 1, 4, 1, 6, ..., and \(\frac{x(1+x^{2})}{(1-x^{2})^{2}} = x + 3x^{3} + 5x^{5} + \cdots\), which added to \(1 + x + x^{2} + \cdots\) gives exactly that. The other numerators fail on these terms: \(x(3 - x^{2})\) and \(2x\) give 3 and 2 as the coefficient of \(x\) instead of 1, and \(x\) gives 2 as the coefficient of \(x^{3}\) instead of 3.

Answer: A

The true formula is \(L_{n} = (\frac{1+\sqrt{5}}{2})^{n} + (\frac{1-\sqrt{5}}{2})^{n}\).

Write \(\varphi = \frac{1+\sqrt{5}}{2}\) and \(\psi = \frac{1-\sqrt{5}}{2}\), the roots of \(x^{2} = x + 1\). Any combination \(a\varphi^{n} + b\psi^{n}\) satisfies the recurrence, so it only remains to match the first two terms. With \(\varphi + \psi = 1\) and \(\varphi\psi = -1\):

\[ \begin{aligned} \varphi + \psi &= 1 = L_{1} \\ \varphi^{2} + \psi^{2} &= (\varphi + \psi)^{2} - 2\varphi\psi = 3 = L_{2} \end{aligned} \]

The difference \(\varphi^{n} - \psi^{n}\) equals \(\sqrt{5}\) at n = 1, not 1; it is \(\sqrt{5}\) times the Fibonacci numbers. The two options with denominator 3 use a number that is not a root of \(x^{2} = x + 1\), so they do not even obey the recurrence; at n = 1 the '+' version gives about 1.21.