08 Sequences and Recurrences Free Online FlashCards

What makes a recursive algorithm correct?

A recursive algorithm needs a base case that is solved directly and a recursive case that reduces the input toward that base case.

Why must a sequence’s starting index be specified?

The starting index matters because the same formula can produce different terms when indexing begins at different values.

What is the general term of an arithmetic sequence?

An arithmetic sequence has constant difference $d$, and its general term is $a_n=a_0+nd$.

How do you sum the first $n+1$ terms of an arithmetic sequence?

The sum of the first $n+1$ terms is $\displaystyle\sum_{k=0}^{n}a_k=\frac{n+1}{2}(a_0+a_n)$.

What is the finite geometric-series formula?

For $r\ne1$, the finite geometric sum is $\displaystyle\sum_{k=0}^{n}a_0r^k=a_0\frac{1-r^{n+1}}{1-r}$.

What is the sum of an infinite geometric series when $|r|<1$?

When $|r|<1$, the infinite geometric series converges to $\displaystyle\sum_{k=0}^{\infty}a_0r^k=\frac{a_0}{1-r}$.

How does summation distribute over a linear combination?

By linearity, $\displaystyle\sum_{k=m}^{n}(cf(k)+dg(k))=c\sum_{k=m}^{n}f(k)+d\sum_{k=m}^{n}g(k)$.

What is the result of a telescoping sum?

If $f(k)=g(k+1)-g(k)$, then $\displaystyle\sum_{k=m}^{n}f(k)=g(n+1)-g(m)$; the intermediate terms cancel.

Reindex $\displaystyle\sum_{k=1}^{n}a_{k-1}$ using $j=k-1$.

Substituting $j=k-1$ changes the expression to $\displaystyle\sum_{j=0}^{n-1}a_j$. The bounds must change with the index.

What is the order of $a_n=4a_{n-1}-a_{n-2}$?

The recurrence $a_n=4a_{n-1}-a_{n-2}$ is second-order because it uses the two preceding terms.

What recurrence counts square-and-domino tilings of a $1\times n$ board?

The tiling count satisfies $a_n=a_{n-1}+a_{n-2}$: a final square leaves an $(n-1)$-board, while a final domino leaves an $(n-2)$-board.

How is the characteristic equation formed?

For a homogeneous recurrence of order $k$, substituting $a_n=r^n$ gives $r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots-c_k=0$.