Functional Equations: Recursion

In one sentence

A function whose domain is the set of positive integers ${\mathbb{N}}_{+}$ is just a sequence: $f(1),f(2),f(3),\dots$. If the functional equation expresses $f(n+1)$ (or $f(n+2)$) in terms of earlier values, it is a recurrence relation. Together with the initial values it determines $f$ completely, and what is left is to find the general term.

Stop 1 · First-order recurrences: add them up

Example. $f:{\mathbb{N}}_{+}\to {\mathbb{N}}_{+}$, $f(m+n)=f(m)+f(n)+mn$, $f(1)=1$.

Put $m=1$: $f(n+1)=f(n)+n+1$. This is a first-order recurrence. The difference between neighboring terms is known, so add them up:

Substitute back into the original equation: $\frac{(m+n)(m+n+1)}{2}=\frac{m(m+1)}{2}+\frac{n(n+1)}{2}+mn$ ✓. This is the same routine as plugging in values on the previous stop: plugging in $m=1$ creates the recurrence, and the recursion method then solves it.

Stop 2 · Second-order recurrences: characteristic roots

This is the example at the start of the page. The key points:

1. If the characteristic equation $x^2=px+q$ has two distinct roots $x_1,x_2$, then $f(n)=c_1{x}_1^n+c_2{x}_2^n$;
2. If it has a double root $x_1$, then $f(n)=(c_1+c_{2}n)x_1^n$;
3. Solve for the constants from $f(1)$ and $f(2)$, and check at the end.

Stop 3 · Double roots

Practice