Recurrences and generating functions

In how many ways can a $1 \times 9$ strip be tiled by $1 \times 1$ squares and $1 \times 2$ dominoes?

Find the characteristic roots of the recurrence $a_{n+2} = a_{n+1} + 6a_n$. Enter them as a set, e.g. 4, -1.

The sequence $(a_n)$ satisfies $a_{n+2} = a_{n+1} + 6a_n$ with $a_0 = 2$ and $a_1 = 1$. Find a closed formula for $a_n$ and use it to compute $a_5$.

Which formula describes all solutions of $a_{n+2} = 6a_{n+1} - 9a_n$ (with $A$, $B$ arbitrary constants)?

The power series $\sum_{n \ge 0} n!\,x^n$ converges only at $x = 0$. Which statement about it, as an element of the ring $\Q[[x]]$ of formal power series, is true?

Which of these statements are true? (Choose all that apply.)

In the proof of Lemma 2 (two solutions of $a_{n+2} = p\,a_{n+1} + q\,a_n$ with the same $a_0$ and $a_1$ agree everywhere), the induction proves the statement "$a_n = b_n$ and $a_{n+1} = b_{n+1}$" rather than just "$a_n = b_n$". Why?

Using the lesson's definition IsSol p q a (meaning ∀ n, a (n + 2) = p * a (n + 1) + q * a n), which Lean statement correctly formalises: every real sequence satisfying $a_{n+2} = a_{n+1} + a_n$ with $a_0 = 0$ and $a_1 = 1$ is the Fibonacci sequence?

In how many ways can the product $x_1 x_2 x_3 x_4 x_5 x_6$ be fully bracketed, keeping the factors in order? (For three factors there are two: $(x_1x_2)x_3$ and $x_1(x_2x_3)$.)

Write series_inverse(a, N) that returns the first N coefficients of $1/A(x)$, where a is the list of coefficients of a power series $A(x)$ with a[0] == 1 (missing coefficients count as $0$). Use the recursion from the Proposition on inverses: $b_0 = 1$ and $b_n = -\sum_{i=1}^{n} a_i b_{n-i}$. Then check that $1/(1 - x - x^2)$ gives the Fibonacci numbers $F_{n+1}$.