Chebyshev, Fibonacci & Generating Functions

Why these topics appear in the Sequences booklet

Beyond routine AP/GP drills, HSC Extension work rewards comfort with linear recurrences. Chebyshev polynomials and Fibonacci numbers are two clean families: each new term is a fixed linear combination of earlier terms. Generating functions then turn the recurrence into algebra.

Chebyshev polynomials of the first kind

Defined by $T_0(x)=1$, $T_1(x)=x$, and

$$T_{n+1}(x)=2x\,T_n(x)-T_{n-1}(x).$$

Worked example 1 — Build $T_2$ and $T_3$

$$T_2(x)=2x\cdot T_1(x)-T_0(x)=2x^2-1,$$ $$T_3(x)=2x(2x^2-1)-x=4x^3-3x.$$

Evaluate $T_3\bigl(\frac12\bigr)$:

$$T_3\bigl(\tfrac12\bigr)=4\cdot\tfrac18-3\cdot\tfrac12=\tfrac12-\tfrac32=-1.$$

Trigonometric view (extension insight): $T_n(\cos\theta)=\cos(n\theta)$ explains roots and composition identities such as $T_m(T_n(x))=T_{mn}(x)$.

Fibonacci and companions

With $F_1=1$, $F_2=1$, $F_n=F_{n-1}+F_{n-2}$, many identities follow from the recurrence alone (e.g. links to Lucas numbers). Treat them as sequence problems: write a few terms, conjecture, prove by induction or by constructing an auxiliary sequence.

Generating functions

A generating function packages a sequence $(a_n)$ into a power series $S(x)=\sum a_n x^n$ (indexing conventions vary). For Fibonacci, algebraic manipulation of $S-xS-x^2S$ using the recurrence produces a rational closed form.

Worked example 2 — Fibonacci generating function (sketch)

If $S(x)=\sum_{n=1}^{\infty} F_n x^{n+1}$ (as in the booklet/blog convention), the recurrence cancels interior coefficients and yields

$$S(x)=\frac{x^2}{1-x-x^2}$$

(for $|x|$ small enough that the series converges). Substituting $x=0.1$ gives $S(0.1)=\frac{1}{89}$, which is why Fibonacci digits appear in the decimal expansion of $\frac{1}{89}$ — with carries explaining digits that are not raw Fibonacci numbers.

Worked example 3 — Discrete calculus teaser

The forward difference $\Delta a_n=a_{n+1}-a_n$ turns summation into a discrete analogue of integration. Sums of powers and telescoping with factorial powers live in the booklet appendices; they connect AP-space problems in Part 2 to a broader toolkit. Open the PDF appendices when you need the full formal development.

Common mistakes

• Off-by-one index errors in the Chebyshev recurrence ($T_{n+1}$ vs $T_n$).
• Evaluating the polynomial before simplifying.
• Generating functions: mismatched powers of $x$ when subtracting $xS$ and $x^2S$.
• Forgetting convergence restrictions when substituting a numeric $x$.

Practice (hints only)

1. Find $T_4(x)$ from the recurrence, then $T_4(1)$.
2. Explain one digit carry in $\frac{1}{89}=0.0112359\ldots$ using $F_6=8$ and $F_7=13$.

Where next

Return to the full Sequences study guide for the TOC, or open the PDF booklet for every worked solution in Part 1 and Part 2. Related teaching articles are linked below and on Vu's QED.