Back to all chapters
# Linear Recurrence Relations

Take your recursion skills to the next level. If you've got a recurrence relation but no computer, how can you find a closed form? What about asymptotic behavior? How fast do rabbits reproduce?

The sequence \(a_0,a_1,a_2,\dots\) satisfies \[a_{m+n} + a_{m-n} = \frac{1}{2}(a_{2m}+a_{2n})\]

for all non-negative integers with \(m\geq n\). If \(a_1 = 1\), determine the value of \[a_{1995}\]

Define a subset \(S\) of the first \(30\) positive integers to be *uneven* if, for all \(i \in S\), \(i+2 \notin S\). For example, \(\{1, 2\}\) is an uneven subset, while \(\{1, 2, 3\}\) is not. If \(N\) represents the number of uneven subsets, find the remainder when \(N\) is divided by \(1000\).

**Notes:**

The empty set is considered to be an uneven subset.

You may want use a calculator at the end.

\[ { \begin{eqnarray} a_{n} & =& 2a_{n-1} + 3 \\ b_{n} &=& b_{n-1} + b_{n-2} \\ \end{eqnarray} } \]

For a positive integer \(n\), consider the two recurrence relations above subjected to the conditions \(a_1 = 0\) and \(b_{1} = b_{2} = 1 \).

If the value of the expression \(\big(a_{b_{2015}} + 3\big)\big(a_{b_{2016}} + 3\big)\) can be expressed as \(p^{b_{q}} \frac{r}{s}\), where \(b_{q}\) is one of the terms in the recurrence relations sequence above and \((p, r)\) and \((r, s)\) are pairwise coprime integers.

Find the value of \((p+q+r+s) \bmod {673}\).

\[ \large a_{n+2} = (n + 3)a_{n+1} - (n + 2)a_{n} \]

For whole numbers \(n\), consider the recurrence relation defined as above with \(a_{1} = 1, a_{2} = 3\).

Find \(\displaystyle\bigg( \sum_{k=1}^{2015} a_{k} \bigg)\pmod{100}.\)

×

Problem Loading...

Note Loading...

Set Loading...