Day 19 — CS Counting & Recurrence Relations

Updated

July 30, 2025

Day 19 — CS Counting & Recurrence Relations

Day 53 — Counting in CS

Stage V · concept day
Goal: Apply product/sum, $P(n,k)$, $\binom{n}{k}$, stars-and-bars, and IE to CS-shaped spaces: passwords, states, hashes, execution trees, bit constraints, protocol messages; reason about size via $\log_2$.

Why this matters

Discrete math earns its keep when you can estimate how big a design space is before you build it. Security entropy, exhaustive test feasibility, hash collision culture, and protocol versioning all reduce to counting. Today is applied fluency—no new hard theorems; tight modeling.

Theory

Modeling checklist

For any CS counting problem:

Name the object (string, function, path, assignment, packet).
Alphabet / domain / codomain sizes.
Order matter? Repetition allowed? Distinguability?
Constraints: forbidden patterns, at-least-one, injectivity, ranges.
Method: product, sum/cases, complement, $P$/$\binom{n}{k}$, stars-bars, IE.
Sanity: small parameters; $\log_2$ of huge answers for “bits of entropy.”

Passwords and keys

Alphabet $\Sigma$, length $k$, rep OK: $|\Sigma|^k$.
No repetition: $P(|\Sigma|,k)$.
Policy “at least one digit”: $|\Sigma|^k - |\Sigma_{\text{letters}}|^k$.
Entropy bits (uniform random password): $\log_2$ of the search space size.
Rough: $36^8$ ≈ $\log_2(36^8)=8\log_2 36\approx 8\cdot 5.17\approx 41.4$ bits.

State spaces

A system with independent fields $f_i\in S_i$ has state space $\prod |S_i|$ (product type).
Illegal combinations: subtract or IE.
Feature flags: $2^n$ configurations; with mutual exclusions, less.

Hash buckets

$n$ distinct keys, $k$ buckets:

All assignments: $k^n$ (functions).
Every bucket nonempty: surjections $k!\,S(n,k)$.
Collision existence: PHP when $n>k$; counts of collision patterns more refined.
Birthday culture: collision probability ~ $1-e^{-n(n-1)/(2k)}$—not pure counting, but $\binom{n}{2}/k$ approx.

Trees of executions

A nondeterministic program with branching factor $b$ and depth $d$: up to $b^d$ leaves (execution traces).
Recursive algorithms: recurrence for number of call-tree nodes (Day 54–55).
Test paths in a CFG: path counting ≠ node counting; loops make infinite paths—bound unwind depth.

Language of bit constraints

Length-$n$ bit-strings:

Constraint	Count
Free	$2^n$
Exactly $k$ ones	$\binom{n}{k}$
No two consecutive ones	Fibonacci (Day 54)
Starts with 10 or ends with 11	IE or cases
Parity even	$2^{n-1}$

Protocol message spaces

A message format: header fields with fixed widths + payload.
Example: version 3 bits, type 5 bits, length 8 bits, flags 4 bits → $2^{3+5+8+4}$ syntactic messages (semantics may forbid many).
TLV / enum tags: sum over cases (sum rule on message type).

Asymptotic size and $\log_2$

When $N$ is huge, report $\log_2 N$ (bits) or $\log_{10} N$ (digits).
Stirling: $\log_2(n!)\approx n\log_2 n - n\log_2 e$ for permutation spaces.
Compare $n^k$ vs $k^n$ vs $n!$ growth for algorithm design (Stage VIII prep).

Function spaces (summary table)

Maps	Count
All $A\to B$	$\\|B\\|^{\\|A\\|}$
Injections	$P(\\|B\\|,\\|A\\|)$
Surjections	IE form
Bijections	$n!$ if equal size
Partial functions	$(\\|B\\|+1)^{\\|A\\|}$ (image or undefined)

Worked examples

Example 1 — Password entropy

8-char passwords from [a-zA-Z0-9]: $62^8$.
$\log_2(62^8)=8\log_2 62\approx 8\cdot 5.95\approx 47.6$ bits.
If only lowercase: $26^8$, $\approx 37.6$ bits—about 10 bits weaker.

Example 2 — PIN policies

4-digit PIN: $10^4=10000$.
Distinct digits: $P(10,4)=5040$.
No leading zero as “number”: $9\cdot 9\cdot 8\cdot 7=4536$ for distinct.

Example 3 — Feature flags with exclusion

10 flags, but flags 1 and 2 cannot both be true: total $2^{10}=1024$; both true: $2^8=256$; valid $1024-256=768$.

Example 4 — IPv4 addresses

$2^{32}$ theoretical; private ranges etc. are subsets. Count $10.0.0.0/8$: $2^{24}$.

Example 5 — Hash assignments

100 keys, 10 buckets: $10^{100}$ total; surjective: $10!\,S(100,10)$ (astronomical; existence of empty buckets almost sure by occupancy theory).

Example 6 — UUID-like

122 random bits (UUID v4 culture): $2^{122}$ possibilities—$\log_2$ is the point.

Example 7 — Execution tree

Binary recursive procedure, depth 10 full tree: $2^{10}=1024$ leaves; $2^{11}-1$ nodes if complete binary.

Example 8 — Bit constraints

Length 8 with no three consecutive 1s—harder (recurrence later). Length 8 exactly 4 ones: $\binom{8}{4}=70$.

Example 9 — Protocol sum rule

Messages of type A (payload 4 bits) or type B (payload 8 bits), 1-bit type tag: $2^4+2^8=16+256=272$ if tag distinguishes; if tag+payload free without structure, different.

Example 10 — API keys

sk_ + 24 chars from 58-char alphabet (Base58 culture): $58^{24}$ keys.

Example 11 — Test matrix

3 browsers × 4 OSes × 2 modes = 24 configurations (product). If one browser-OS pair unsupported: $24-2=22$ if 2 modes still apply.

Example 12 — Semantic versioning space

major.minor.patch with major $0..9$, minor $0..99$, patch $0..99$: $10\cdot 100\cdot 100=100{,}000$ version triples.

Example 13 — Partial functions

Functions from 5 endpoints to 3 handlers or “unhandled”: $4^5$.

Example 14 — Log compare

Which larger: $20!$ or $2^{60}$? $\log_2(20!)\approx \sum_{k=1}^{20}\log_2 k \approx 61.1$ roughly—comparable to $2^{60}$. (Actual $20!\approx 2.43\times 10^{18}$, $2^{60}\approx 1.15\times 10^{18}$.)

Example 15 — Restricted passwords IE

Length 6 from 62 chars, must include ≥1 digit AND ≥1 letter:
total $62^6$ − pure digits $10^6$ − pure letters $52^6$ + empty? (can’t be both pure digit and pure letter unless empty set): $+0$.
Wait pure digit ∩ pure letter = empty for length 6. So $62^6-10^6-52^6$.

Exercises

Entropy bits of 12-char lowercase passwords.
6-char alphanumeric, at least one digit—expression.
State space: 4 enums of sizes 3,3,5,2; one forbidden combo—count.
$n$ bits, Hamming weight ≤ 2: sum of binomials.
Number of injections from 8 users to 100 user-IDs.
Surjective assignment of 12 shards to 4 racks.
Binary strings length 10 starting with 1 or containing 00 as suffix—careful.
Estimate $\log_2(52!)$ for a shuffled deck (approx OK).
Message: 16-bit header free + 3-bit type; for types 0,1 payload 8 bits; type 2–7 payload 0—count valid messages.
Feature flags 12 with at most 3 true: $\sum_{k=0}^{3}\binom{12}{k}$.
Compare $2^{40}$ vs $3^{25}$ via logs.
CFG: 3 branches then 2 then 2—trace count if no merge.
Hash: 365 days, 30 people—birthday count culture $\binom{30}{2}/365$ approx expected colliding pairs.
IPv6 address bits and $\log_2$.
Partial maps $[n]\to[m]$ count.
Passwords length ≤ 4 from 26 letters (sum rule on length).
Number of $n\times n$ binary matrices; with all row sums 1 (permutation matrices if also cols).
CS: count distinct git short hashes if 7 hex chars: $16^7$.
Protocol versioning: 2-bit major, 4-bit minor—how many?
At least one of three error flags set in a byte of flags (8 flags)—set up.
Why exhaustive test of $2^{64}$ states is infeasible—time argument.
Derangement secret santa for 10 engineers.
Multiset of 5 config options from 3 modes (stars-bars).
Challenge: count valid UTF-8 code units patterns lite—or count 4-byte sequences with high bit constraints you invent.
Write a one-page “threat model entropy” for a 6-digit OTP vs 8-char base32 secret.

CS connection

This is the CS connection day:

Security: password/key space size.
Testing: combinatorial coverage.
Distributed systems: assignment and partition counts.
Networking: address and header spaces.
Languages: string constraints and automata-accepted counts (awareness).

Common pitfalls

Pitfall	What to do instead
Counting syntax not semantics	State whether invalid messages excluded
Entropy as character count	Use $\log_2$ of space
Birthday as PHP certainty	PHP vs probability
Forgetting policies that shrink space	Complement / IE
$k^n$ vs $n^k$ mix-up	Domain→codomain: $\\|B\\|^{\\|A\\|}$

Checkpoint

Password + entropy calculation cold
Function space table from memory
One IE policy password
One protocol product/sum
$\log_2$ comparison of two huge numbers
Exercises 1–15
Modeling checklist used on a system you know

Two personal takeaways:

Selected mini-solutions

$12\log_2 26\approx 56.4$ bits.
$62^6-52^6$.
$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}$.
$P(100,8)$.
Stirling $\approx 52\ln 52-52$ nats → convert; ~225.7 bits.
$1+12+66+220=299$.
$26+26^2+26^3+26^4$.
$16^7=268{,}435{,}456$.
$!10=1{,}334{,}961$.

Deepening notes

Entropy quick reference

\[ H_{\text{bits}}=\log_2|\text{search space}| \]

for uniform random secrets. Real user-chosen passwords are far from uniform—counts give upper bounds on attacker work only under uniform assumptions.

Occupancy and empty buckets

Throw $n$ balls into $k$ bins: expected empty bins $k(1-1/k)^n\approx k e^{-n/k}$. Surjection count is exact but huge; occupancy asymptotics guide system design.

Protocol grammar counting

If messages are a disjoint union of formats $F_i$ each a product of field alphabets, total syntactic messages $=\sum_i\prod_j |A_{ij}|$. Semantic validity is a subset—state which you count.

CFG path explosion

A loop with $b$ branches body and up to $L$ iterations can contribute $\sim b^L$ paths. Bounded model checking and coverage metrics exist because full path enumeration dies.

Extra drills

D1. Entropy of 6-digit OTP vs 128-bit key.
D2. $2^{48}$ vs $10^{14}$ via logs.
D3. Config: 3 enums (5,5,5) with 10 forbidden triples.
D4. Injections users→IDs: 50 users, 1000 IDs.
D5. Bit-strings length 12 weight ≤3.
D6. State machine 4 registers 2-bit each: state count.
D7. Git short hash 8 hex: collision PHP threshold.
D8. Partial functions $[8]\to[3]$.

Modeling card (carry forward)

Name object 2. Alphabet 3. Order/rep 4. Constraints 5. Method 6. $\log_2$ sanity.

Worked case study — API key design

Spec: live_ prefix + 24 chars from Base58 (58 symbols).
Space: $58^{24}$.
Bits: $24\log_2 58\approx 24\cdot 5.858\approx 140.6$ bits.
If no character repeats: $P(58,24)$—slightly smaller, harder to type-check.
Policy “must include digit”: Base58 includes digits; if separate classes, use complement.

Worked case study — feature rollout matrix

Browsers 4 × OS 3 × locales 5 = 60 configs.
Drop IE on Linux (1 browser × 1 OS × 5 locales = 5): 55.
Product then subtract—document the illegal rectangle.

Comparison table growth

Expression	$\log_2$ scale
$2^n$	$n$
$n!$	$\sim n\log_2 n$
$n^n$	$n\log_2 n$
$C_n$	$\sim 2n - \tfrac32\log_2 n$ culture

Exam drill block

E1. Entropy bits of a 16-character password from 62 symbols (uniform).
E2. Compare $2^{40}$ and $10^{12}$ via $\log_{10}$ or $\log_2$.
E3. Config space: 5 booleans × enum of 4 × enum of 3, minus 6 illegal pairs.
E4. Number of injections from 8 users to 1000 IDs: $P(1000,8)$.
E5. Bit-strings length 16 with weight ≤2.
E6. State machine: 3 registers, each 4 states—$|S|$.
E7. Short hash 6 hex chars: birthday threshold $\sim\sqrt{\pi 16^6/2}$ order-of-magnitude.
E8. Partial functions $[n]\to[k]$: count $(k+1)^n$.
E9. True/false: (i) $\log_2$ of space is bits of uniform secret (ii) path explosion is always $n!$ (iii) occupancy uses $k^n$ as total throws.
E10. Protocol: 8-bit type field; if type $<128$ payload is 16 bytes else 4 bytes—total message count.

Mini solutions

E1. $16\log_2 62\approx 16\cdot 5.95\approx 95.3$ bits.
E2. $2^{40}\approx 1.1\cdot 10^{12}$—same order.
E3. $2^5\cdot 4\cdot 3-6=384-6=378$ if illegal are single configs.
E5. $\binom{16}{0}+\binom{16}{1}+\binom{16}{2}=1+16+120=137$.
E6. $4^3=64$.
E8. Yes $(k+1)^n$ if “undefined” is extra image.
E9. T; F; T (each ball chooses a bin).
E10. $128\cdot 2^{128}+128\cdot 2^{32}$ if payload is free bits—state bit model carefully.

Modeling card (reprise)

Name the object (password, state, path, key).
Alphabet / component sizes.
Order? Repetition? Constraints?
Product / sum / complement / IE / $P(n,k)$ / $\binom{n}{k}$.
Sanity: $\log_2$ and small-$n$ check.

Synthesis

CS counting converts specs into search spaces: passwords and keys (entropy), configs (product − forbidden), hashes (birthday), programs (path trees), protocols (sum of products). Prefer exact formulas; use $\log_2$ for scale. Uniformity assumptions are explicit—real systems often fall short.

S1. Design a token: prefix + Base64 body; report bits.
S2. Count feature-flag assignments with “at most 3 true.”
S3. Cold: $62^8$ bits; surjective hash of 5 keys into 3 buckets.

Tomorrow

Day 54 — Recurrences intro: definitions, Fibonacci, Hanoi, merge-sort style setup, base cases.

Day 54 — Recurrences intro

Stage V · concept day
Goal: Define sequences by recurrence; identify linear homogeneous relations; set up Fibonacci, Tower of Hanoi, tiling, and divide-and-conquer recurrences; enforce base-case discipline.

Why this matters

Algorithms that call themselves, structures that grow by local rules, and counting problems with “last step” cases produce recurrences. Before solving (Day 55), you must set them up correctly: domain, order, base cases, and what $a_n$ means. A wrong base case poisons every later term.

Theory

What is a recurrence?

A recurrence relation defines each term of a sequence using previous terms. Example:

\[ a_n = 2a_{n-1} + 1,\qquad a_0=0. \]

The relation + base case(s) determine the sequence uniquely (when well-posed).

Explicit vs recursive definition

Closed form / explicit: $a_n=2^n-1$ (formula in $n$ only).
Recursive: defined from earlier values.
Day 55 converts many linear recurrences to closed forms.

Order and homogeneity

Order $k$: $a_n$ depends on $a_{n-1},\ldots,a_{n-k}$ (needs $k$ bases).
Linear: $a_n$ is a linear combination of previous terms plus optional $f(n)$.
Homogeneous: $f(n)=0$ (no extra forcing term).
Constant coefficients: coefficients do not depend on $n$.

Example: $a_n=a_{n-1}+a_{n-2}$ — linear homogeneous order 2, constant coeffs (Fibonacci-like).
Example: $a_n=3a_{n-1}+2^n$ — linear nonhomogeneous.
Example: $a_n=n a_{n-1}$ — linear, variable coefficient.

Domain of the recurrence

State for which $n$ the relation holds (often $n\ge 2$ or $n\ge 1$).
Base cases cover the smallest $n$ outside that range.
Never apply the recurrence below its domain.

Fibonacci sequence

Standard indexing variants exist—fix yours:

\[ F_0=0,\; F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\ (n\ge 2). \]

So $0,1,1,2,3,5,8,13,21,34,\ldots$.

Counting story: number of ways to tile a $1\times n$ board with tiles of size 1 and 2: $T_n=T_{n-1}+T_{n-2}$, $T_0=1$, $T_1=1$, so $T_n=F_{n+1}$.

Bit-strings length $n$ with no two consecutive 1s: $a_n=a_{n-1}+a_{n-2}$ (end with 0: $a_{n-1}$ ways; end with 01… wait end with 0: $a_{n-1}$; end with 1: must …01, $a_{n-2}$). Bases: $a_1=2$ (0,1), $a_2=3(00,01,10`).

Tower of Hanoi

Move $n$ disks from peg A to C, spare B; never larger on smaller.

\[ H_n = 2H_{n-1} + 1,\qquad H_0=0\ (H_1=1). \]

Story: move $n-1$ to spare ($H_{n-1}$), move largest to target ($1$), move $n-1$ onto target ($H_{n-1}$).
Closed form preview: $H_n=2^n-1$.

Merge-sort style recurrence

Sorting $n$ elements by split, recurse, merge:

\[ T(n)=2T(n/2)+cn,\qquad T(1)=\Theta(1), \]

for $n$ a power of 2 (setup; solving Day 55 / Master theorem Stage VIII).
Meaning: two half-size subproblems + linear merge work.

Binary search: $T(n)=T(n/2)+\Theta(1)$.

Last-step counting pattern

To count structures of size $n$:

Classify by a feature of the “end” or a distinguished piece.
Express counts in terms of smaller sizes.
Fix bases by enumeration.

Uniqueness / well-posedness

Given order-$k$ linear recurrence with fixed coefficients and $k$ consecutive initial values, there is a unique infinite sequence satisfying them.

Generating values by hand

Table method: write $n$ | $a_n$ and fill using the relation. Check bases twice.

Worked examples

Example 1 — Fibonacci table

$F_0..F_{10}$: 0,1,1,2,3,5,8,13,21,34,55.

Example 2 — Tiling

$T_n$ tilings of $n$-board with 1s and 2s: $T_0=1,T_1=1,T_2=2,T_3=3,T_4=5,T_5=8$.

Example 3 — Hanoi

$H_1=1,H_2=3,H_3=7,H_4=15=2^4-1$.

Example 4 — Bit-strings no consecutive 1s

$a_1=2,a_2=3,a_3=a_2+a_1=5,a_4=8,a_5=13$.

Example 5 — Set up only

Number of ways to climb $n$ stairs taking 1 or 2 steps: same as tiling $T_n$.

Example 6 — Nonhomogeneous

$a_n=2a_{n-1}+1$, $a_0=0$: compute $0,1,3,7,15$ → guess $2^n-1$.

Example 7 — Factorial recurrence

$n!=n\cdot(n-1)!$, $0!=1$—variable coefficient, solution is factorial.

Example 8 — Regions (optional classic)

Maximum regions by $n$ lines in general position: $R_n=R_{n-1}+n$, $R_0=1$.
($R_n=1+n(n+1)/2$.)

Example 9 — Merge sort expand

$T(n)=2T(n/2)+n$, $T(1)=0$:
$T(n)=n+2T(n/2)=n+2(n/2+2T(n/4))=\cdots=n\log_2 n$ for $n=2^k$.

Example 10 — Wrong bases

If $F_0=1,F_1=1$ then you get $1,1,2,3,5,\ldots$ (often called Fibonacci too—indexing shift). State clearly.

Example 11 — Strings over ternary

Length $n$ over $\{0,1,2\}$ no two consecutive equal: $a_n=3\cdot 2^{n-1}$ closed; recurrence $a_n=2a_{n-1}$, $a_1=3$.

Example 12 — Derangement recurrence

$!n=(n-1)[!(n-1)+!(n-2)]$ with $!0=1,!1=0$—order 2, non-constant-looking but standard.

Example 13 — Catalan recurrence

$C_0=1$, $C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}$—nonlinear (quadratic). Not linear constant coeff.

Example 14 — Domain care

$a_n=a_{n-1}+2a_{n-2}$ for $n\ge 2$ needs $a_0,a_1$. If someone gives only $a_1$, sequence not determined.

Example 15 — CS call tree

$C(n)=C(n-1)+C(n-2)+1$ counting nodes in Fib recursion tree—different from Fib values themselves.

Exercises

Compute $F_{12}$ from bases.
Tiling $T_8$ with singles and dominoes.
Hanoi $H_6$ and verify $2^6-1$.
Bit-strings length 6 no consecutive 1s.
Set up recurrence for ways to write $n$ as ordered sum of 1s and 2s (compositions).
$a_n=3a_{n-1}$, $a_0=5$: list to $a_5$; guess closed form.
$a_n=a_{n-1}+n$, $a_0=0$: compute to $a_6$; closed form?
Why does order 2 need two bases? Counterexample with one base.
Merge sort: expand $T(16)$ with $T(n)=2T(n/2)+n$, $T(1)=0$.
Binary search $T(n)=T(\lfloor n/2\rfloor)+1$, $T(1)=1$: value at $n=16$.
Climb stairs 1, 2, or 3 at a time: recurrence + bases; $a_5$.
Strings length $n$ over $\{0,1\}$ ending with 0 vs 1—system of recurrences optional.
Regions $R_n=R_{n-1}+n$, $R_0=1$: closed form.
Explain why Catalan recurrence is not linear.
Set up $a_n$ for perfect binary tree height $n$ node count.
CS: number of calls to compute Fib($n$) naively—recurrence.
$a_n=na_{n-1}$, $a_0=1$: what is $a_n$?
Write bases wrong on purpose for Hanoi and show damage at $n=4$.
Multistep: define $a_n=2^n$ both closed and as recurrence.
No two consecutive equal letters from 26-letter alphabet length $n$.
Longest path counting? (skip)—instead: number of subsets of $[n]$ via recurrence $a_n=2a_{n-1}$.
Domain: for $a_n=a_{n/2}+1$ ($n$ even), what bases and domain issues?
Challenge: recurrence for derangements $!n=n\cdot!(n-1)+(-1)^n$.
Table: compute 10 terms of $a_n=2a_{n-1}-a_{n-2}$, $a_0=1,a_1=3$.
Story: number of binary strings length $n$ with no 011—set up states (harder) or skip to: no 00 only.

CS connection

Runtime recurrences: divide-and-conquer algorithms.
Dynamic programming: DP is organized recurrence evaluation.
Data structure sizes: tree node counts, path lengths.
Combinatorial generation: recursive structure of objects (trees, tilings).
Loop invariants cousin: recurrences describe discrete time evolution of state counts.

Common pitfalls

Pitfall	What to do instead
Missing or wrong bases	Enumerate small $n$ carefully
Off-by-one in “size $n$” meaning	Define $a_n$ in words first
Applying recurrence for $n$ too small	State domain $n\ge n_0$
Indexing Fibonacci inconsistently	Fix $F_0,F_1$ in writing
Confusing $T(n)$ time with $a_n$ counts	Separate notations
Nonlinear treated as linear	Catalan ≠ characteristic eq method

Checkpoint

Define order, linear, homogeneous
Fib, tiling, Hanoi setups with bases
Merge-sort recurrence meaning
Build a table of 8+ terms for a custom recurrence
Exercises 1–15
Explain base-case discipline in one sentence

Two personal takeaways:

Selected mini-solutions

$F_{12}=144$.
$T_8=F_9=34$.
$H_6=63$.
$a_6=21$ if $a_1=2,a_2=3$ Fib-like.
$a_n=5\cdot 3^n$.
$a_n=n(n+1)/2$.
$T(16)=16\cdot 4=64$ if $T(n)=n\log_2 n$ with $T(1)=0$.
$T(16)=5$ (five halvings to 1? $16\to8\to4\to2\to1$: 4 steps + base—define carefully: often $1+\log_2 n$).
$a_n=a_{n-1}+a_{n-2}+a_{n-3}$, $a_0=1,a_1=1,a_2=2$, $a_5=13$.
$a_n=n!$.

Deepening notes

Base-case audit procedure

Write $a_n$ in English (“number of … of size $n$”).
Compute $a_0$ or $a_1$ by listing.
Verify the recurrence at the smallest $n$ in its domain by listing both sides.
Only then compute further terms.

Fibonacci indexing wars

Some authors set $F_1=F_2=1$. Then their $F_n$ is your $F_n$ shifted. Always restate bases when quoting formulas (Binet is index-sensitive).

From recurrence to algorithm cost

$T(n)=2T(n/2)+n$ is merge sort; $T(n)=T(n-1)+n$ is insertion-sort style; $T(n)=T(n-1)+T(n-2)+O(1)$ is naive Fib time (exponential). The recurrence is the model of the algorithm’s call structure.

Extra drills

D1. Table $F_0..F_{15}$.
D2. $T_n$ tilings through $n=10$.
D3. Stairs 1 or 2 steps: $a_{10}$.
D4. $H_8=2^8-1$.
D5. No consecutive 1s strings length 8.
D6. $a_n=a_{n-1}+2a_{n-2}$, $a_0=1,a_1=1$ ten terms.
D7. Wrong base $H_0=1$—how $H_3$ breaks vs $2^n-1$.
D8. Set up recurrence for binary strings with no 000.

Flash

Order $k$ needs $k$ bases; Fib $F_n=F_{n-1}+F_{n-2}$; Hanoi $H_n=2H_{n-1}+1$; Merge $T(n)=2T(n/2)+n$.

Exam drill block

E1. Define order, linear, homogeneous, constant coefficients—with examples.
E2. Fib table to $F_{15}$; tiling $T_{10}$.
E3. Hanoi recurrence + closed form guess; verify $n=5$.
E4. No consecutive 1s: bases + $a_7$.
E5. Stairs 1/2/3: bases + $a_6$.
E6. Merge-sort expand $T(32)$.
E7. $a_n=3a_{n-1}+1$, $a_0=0$—compute 6 terms; guess form.
E8. Why Catalan recurrence is nonlinear.
E9. Domain error: apply $a_n=a_{n-1}+a_{n-2}$ at $n=1$ wrongly—show mess.
E10. CS: naive recursive Fib call count recurrence.

Mini solutions

E3. $H_5=31$.
E4. $a_7=34$ if $a_1=2,a_2=3$.
E6. $32\cdot 5=160$ idealized $n\log_2 n$.

Worked setup gallery

W1 — Tilings. $T_n=$ ways to tile $n$-board with $1$s and $2$s: $T_n=T_{n-1}+T_{n-2}$, $T_0=1,T_1=1$. Same as Fib shifted.

W2 — Hanoi. $H_n=2H_{n-1}+1$, $H_0=0$ or $H_1=1$ → closed $2^n-1$.

W3 — Merge sort cost. $T(n)=2T(n/2)+n$ for $n=2^k$, $T(1)=0$ → $T(n)=n\log_2 n$.

W4 — No consecutive 1s. $a_n=a_{n-1}+a_{n-2}$ (end in 0: $a_{n-1}$; end in 01… wait end in 1 ⇒ prev 0): standard Fib-like with $a_1=2,a_2=3$.

W5 — Stairs 1/2/3. $a_n=a_{n-1}+a_{n-2}+a_{n-3}$ with three base cases by listing.

Synthesis

A recurrence is a definition by smaller instances. Get order, linearity, and bases right before computing. Fibonacci family covers tilings and bit-strings; Hanoi and divide-and-conquer show algorithm costs. Listing small $n$ is the base-case audit. Closed forms wait for Day 55.

S1. Set up and tabulate no-11 bit-strings through length 8.
S2. Write Hanoi recurrence, prove $H_n=2^n-1$ by induction.
S3. Cold: $F_{10}$, $T_8$ tilings, $H_7$.

Checklist before solving (Day 55)

Domain of $n$ stated
Exactly $k$ bases for order $k$
Recurrence verified at smallest legal $n$
Homogeneous vs inhomogeneous noted
Algorithm cost vs combinatorial count distinguished

Tomorrow

Day 55 — Solving recurrences: characteristic equation, first-order linear, generating functions lite.

Day 55 — Solving recurrences

Stage V · concept day
Goal: Solve first-order linear and second-order linear homogeneous recurrences with constant coefficients; use summation-factor idea; meet ordinary generating functions lite (Fibonacci GF sketch).

Why this matters

Closed forms turn “$T(n)=2T(n/2)+n$” into “$\Theta(n\log n)$” and “$F_n$” into Binet. Generating functions package infinite sequences into algebra—later probability and combinatorics use them heavily. Today: practical solution recipes + GF awareness, not full theory.

Theory

First-order linear homogeneous

\[ a_n = c\, a_{n-1},\qquad a_0=A \implies a_n = A\, c^n. \]

If $a_1=A$ as base: $a_n=A c^{n-1}$.

First-order linear nonhomogeneous (constant inhomogeneity)

\[ a_n = c\, a_{n-1} + d,\qquad c\neq 1. \]

Equilibrium / particular solution: constant $a=c a+d\Rightarrow a=d/(1-c)$.
General: $a_n = K c^n + \frac{d}{1-c}$.
Fit $K$ from base case.

If $c=1$: $a_n=a_{n-1}+d\Rightarrow a_n=a_0+nd$.

Summation idea: unfold

\[ a_n=c a_{n-1}+d=c(c a_{n-2}+d)+d=\cdots=c^n a_0+d\sum_{j=0}^{n-1}c^j=c^n a_0+d\frac{c^n-1}{c-1}\ (c\neq 1). \]

Second-order linear homogeneous

\[ a_n = p\, a_{n-1} + q\, a_{n-2},\qquad n\ge 2. \]

Characteristic equation:

\[ r^2 - p r - q = 0. \]

Case 1: two distinct roots $r_1,r_2$.

\[ a_n = A r_1^n + B r_2^n. \]

Solve $A,B$ from $a_0,a_1$.

Case 2: repeated root $r$.

\[ a_n = (A+Bn)r^n. \]

Fibonacci closed form (Binet)

$F_n=F_{n-1}+F_{n-2}$, $F_0=0,F_1=1$.
Characteristic: $r^2-r-1=0$, roots $\phi=\frac{1+\sqrt{5}}{2}$, $\hat\phi=\frac{1-\sqrt{5}}{2}$.
$F_n=A\phi^n+B\hat\phi^n$; $F_0=0\Rightarrow B=-A$; $F_1=1\Rightarrow A(\phi-\hat\phi)=1\Rightarrow A=1/\sqrt{5}$.
Thus

\[ F_n = \frac{\phi^n-\hat\phi^n}{\sqrt{5}}. \]

Nearest integer to $\phi^n/\sqrt{5}$ for $n\ge 1$.

Hanoi closed form

$H_n=2H_{n-1}+1$, $H_0=0$: from first-order recipe, $H_n=2^n-1$.

Divide-and-conquer (unfolding lite)

$T(n)=2T(n/2)+n$, $n=2^k$, $T(1)=\Theta(1)$:

\[ T(n)=n+2\cdot\frac{n}{2}+4\cdot\frac{n}{4}+\cdots+n\cdot T(1)=n\log_2 n+O(n). \]

Master theorem (Stage VIII) generalizes.

Ordinary generating functions (lite)

The ordinary generating function (OGF) of $(a_n)_{n\ge 0}$ is

\[ A(x)=\sum_{n=0}^{\infty} a_n x^n. \]

Algebra of OGFs (awareness):

$A+B$ ↔︎ termwise sum;
$xA(x)$ ↔︎ shift right (roughly);
$1/(1-x)=\sum x^n$;
$1/(1-cx)=\sum c^n x^n$.

Fibonacci GF derivation sketch

Let $F(x)=\sum_{n\ge 0} F_n x^n$ with $F_0=0,F_1=1$.
From $F_n=F_{n-1}+F_{n-2}$ ($n\ge 2$):

\[ F(x)-F_0-F_1 x = x(F(x)-F_0)+x^2 F(x). \]

So $F(x)-x = x F(x)+x^2 F(x)$, hence

\[ F(x)=\frac{x}{1-x-x^2}. \]

Extract coefficients: partial fractions using roots of $1-x-x^2=0$, recover Binet—sketch only.

Simple coefficient extraction

$\sum\binom{n}{k}x^k=(1+x)^n$ finite.
$[x^n]\frac{1}{(1-x)^{k+1}}=\binom{n+k}{k}$ (negative binomial / stars-and-bars link).

Worked examples

Example 1 — Geometric

$a_n=5a_{n-1}$, $a_0=2$ → $a_n=2\cdot 5^n$.

Example 2 — Affine

$a_n=3a_{n-1}+2$, $a_0=1$.
Particular: $a=3a+2\Rightarrow a=-1$.
General: $a_n=K\cdot 3^n-1$. $a_0=1\Rightarrow K-1=1\Rightarrow K=2$.
$a_n=2\cdot 3^n-1$. Check: $a_1=5$, $3\cdot 1+2=5$.

Example 3 — Summation unfold

$a_n=2a_{n-1}+1$, $a_0=0$: $a_n=\sum_{j=0}^{n-1}2^j=2^n-1$.

Example 4 — Characteristic distinct

$a_n=5a_{n-1}-6a_{n-2}$, $a_0=0,a_1=1$.
$r^2-5r+6=0=(r-2)(r-3)$.
$a_n=A\cdot 2^n+B\cdot 3^n$.
$A+B=0$, $2A+3B=1\Rightarrow A=-1,B=1$.
$a_n=3^n-2^n$.

Example 5 — Fibonacci check

$F_5=\frac{\phi^5-\hat\phi^5}{\sqrt{5}}=5$.

Example 6 — Repeated root

$a_n=4a_{n-1}-4a_{n-2}$, $a_0=1,a_1=4$.
$(r-2)^2=0$. $a_n=(A+Bn)2^n$.
$A=1$; $a_1=(A+B)2=4\Rightarrow A+B=2\Rightarrow B=1$.
$a_n=(1+n)2^n$.

Example 7 — Hanoi

Already $2^n-1$.

Example 8 — Merge sort

$T(32)=32\cdot 5=160$ if $T(n)=n\log_2 n$ with zero base cost idealized.

Example 9 — GF geometric

$a_n=3^n$: $A(x)=1/(1-3x)$ for $|3x|<1$ formally.

Example 10 — Stars-bars GF

Number of nonnegative solutions $x_1+\cdots+x_k=n$ is $[x^n](1-x)^{-k}=\binom{n+k-1}{k-1}$.

Example 11 — Fit constants carefully

$a_n=a_{n-1}+2a_{n-2}$, $a_0=3,a_1=1$.
$r^2-r-2=0=(r-2)(r+1)$.
$a_n=A 2^n+B(-1)^n$.
$A+B=3$, $2A-B=1\Rightarrow A=\frac{4}{3},B=\frac{5}{3}$. Wait: $A+B=3$, $2A-B=1$ add: $3A=4$, $A=4/3$, $B=5/3$. Check $a_2=a_1+2a_0=1+6=7$; formula $(4/3)4+(5/3)=16/3+5/3=7$.

Example 12 — Nonhomogeneous polynomial (awareness)

$a_n=2a_{n-1}+n$: particular of form $An+B$; solve and add homogeneous $K\cdot 2^n$. (Optional practice.)

Example 13 — Partial fractions lite

$F(x)=x/(1-x-x^2)$ factors as $c_1/(1-\phi x)+c_2/(1-\hat\phi x)$—leads to Binet.

Example 14 — Verify by induction

Prove $a_n=2\cdot 3^n-1$ satisfies Ex. 2 by induction after guessing.

Example 15 — Catalan GF awareness

$C(x)=\sum C_n x^n$ satisfies $C=1+x C^2$—quadratic, not linear recurrence method.

Exercises

Solve $a_n=7a_{n-1}$, $a_0=3$.
Solve $a_n=2a_{n-1}+5$, $a_0=1$.
Solve $a_n=a_{n-1}+4$, $a_0=2$.
Characteristic roots for $a_n=a_{n-1}+6a_{n-2}$.
Solve $a_n=5a_{n-1}-6a_{n-2}$, $a_0=0,a_1=1$ (Ex. 4 style—already).
Solve $a_n=6a_{n-1}-9a_{n-2}$, $a_0=1,a_1=3$.
Binet: compute $F_6$ via formula (should be 8).
Prove by induction $H_n=2^n-1$.
Unfold $T(n)=2T(n/2)+n$ for $n=2^k$ to closed form.
Write OGF for $a_n=1$ all $n$; for $a_n=n$.
Show $[x^n](1-x)^{-3}=\binom{n+2}{2}$.
Derive $F(x)=x/(1-x-x^2)$ carefully from scratch.
Solve $a_n=4a_{n-1}$, $a_2=5$ (careful with index).
$a_n=3a_{n-1}+2^n$—try particular $K\cdot 2^n$ (note if 2 is root of homogeneous).
Fib: solve with $F_0=0,F_1=1$ for $A,B$ again.
Sequence $1,2,4,8,\ldots$ recurrence + closed.
$a_n=2a_{n-1}-a_{n-2}$, $a_0=5,a_1=5$—what sequence?
CS: closed form for number of subsets $2^n$ from recurrence $a_n=2a_{n-1}$.
Master-ish: $T(n)=3T(n/3)+n$, unfold sketch.
GF: extract $[x^4]$ of $1/(1-x-x^2)$ (related to Fib).
Repeated root example of your own with numbers.
Why characteristic method fails for $a_n=n a_{n-1}$.
Challenge: full particular solution for $a_n=2a_{n-1}+n$.
Limit $F_{n+1}/F_n\to\phi$.
Write a 5-step recipe card for order-2 homogeneous solving.

CS connection

Runtime closed forms from recurrences.
Amortized analysis cousin: unfolding sums.
Digital signal / linear filters: same linear recurrences.
Generating functions in combinatorics on words and probability pgfs (later).
Compiler loop strength reduction culture: closed forms of induction variables.

Common pitfalls

Pitfall	What to do instead
Wrong characteristic polynomial sign	$r^2-pr-q=0$ for $a_n=pa_{n-1}+qa_{n-2}$
Forgetting to solve for $A,B$	Use both bases
Repeated root missing $n$ factor	$(A+Bn)r^n$
$c=1$ case of $a_n=ca_{n-1}+d$	Arithmetic sequence
GF as values not formal series	Coefficient extraction mindset
Applying to nonlinear Catalan	Different methods

Checkpoint

Two personal takeaways:

Selected mini-solutions

$a_n=3\cdot 7^n$.
Particular $-5$; $a_n=K\cdot 2^n-5$; $K=6$; $a_n=6\cdot 2^n-5$.
$a_n=2+4n$.
$r^2-r-6=0$, $r=3,-2$.
$(r-3)^2$; $a_n=(1+0\cdot n)3^n=3^n$ if $a_1=3$—check $a_1=(A+B)3=3\Rightarrow A+B=1$, $A=1,B=0$.
$1/(1-x)$; $x/(1-x)^2$.
Constant 5 (double root 1: $a_n=A+Bn$, $B=0$).
$[x^4]F(x)/x$ related—$[x^4]1/(1-x-x^2)=F_5=5$ if $1/(1-x-x^2)=\sum F_{n+1}x^n$.

Deepening notes

Recipe card — order 2 homogeneous

Write $a_n - p a_{n-1} - q a_{n-2}=0$.
Characteristic $r^2-pr-q=0$.
Distinct roots: $A r_1^n+B r_2^n$; repeated: $(A+Bn)r^n$.
Solve $A,B$ from $a_0,a_1$.
Verify $a_2$ by both recurrence and closed form.

Unfolding template order 1

$a_n=c a_{n-1}+d = c^n a_0 + d\sum_{j=0}^{n-1}c^j$.
Geometric sum closed form depending on $c=1$ or not.

GF coefficient dictionary

OGF	$[x^n]$
$1/(1-x)$	$1$
$1/(1-cx)$	$c^n$
$x/(1-x)^2$	$n$
$1/(1-x)^{k+1}$	$\binom{n+k}{k}$
$x/(1-x-x^2)$	$F_n$

Extra drills

D1. $a_n=4a_{n-1}+3$, $a_0=0$.
D2. $a_n=a_{n-1}+6a_{n-2}$, $a_0=3,a_1=1$.
D3. Binet $F_7=13$ check.
D4. Prove $H_n=2^n-1$ by induction.
D5. Unfold $T(n)=2T(n/2)+3n$.
D6. GF for $a_n=2^n$.
D7. Repeated root: $a_n=2a_{n-1}-a_{n-2}$, $a_0=1,a_1=3$.
D8. Partial fractions sketch for Fib GF.

Flash

$r^2-pr-q=0$; $F_n=(\phi^n-\hat\phi^n)/\sqrt5$; $F(x)=x/(1-x-x^2)$.

Tomorrow

Day 56 — Story proofs: combinatorial vs algebraic; double counting; bijections; hockey-stick.

Expression	\(\log_2\) scale
\(2^n\)	\(n\)
\(n!\)	\(\sim n\log_2 n\)
\(n^n\)	\(n\log_2 n\)
\(C_n\)	\(\sim 2n - \tfrac32\log_2 n\) culture

OGF	\([x^n]\)
\(1/(1-x)\)	\(1\)
\(1/(1-cx)\)	\(c^n\)
\(x/(1-x)^2\)	\(n\)
\(1/(1-x)^{k+1}\)	\(\binom{n+k}{k}\)
\(x/(1-x-x^2)\)	\(F_n\)

Day 19 — CS Counting & Recurrence Relations

Day 53 — Counting in CS

Why this matters

Theory

Modeling checklist

Passwords and keys

State spaces

Hash buckets

Trees of executions

Language of bit constraints

Protocol message spaces

Asymptotic size and \(\log_2\)

Function spaces (summary table)

Worked examples

Exercises

CS connection

Common pitfalls

Checkpoint

Selected mini-solutions

Deepening notes

Entropy quick reference

Occupancy and empty buckets

Protocol grammar counting

CFG path explosion

Extra drills

Modeling card (carry forward)

Worked case study — API key design

Worked case study — feature rollout matrix

Comparison table growth

Exam drill block

Mini solutions

Modeling card (reprise)

Synthesis

Tomorrow

Day 54 — Recurrences intro

Why this matters

Theory

What is a recurrence?

Explicit vs recursive definition

Order and homogeneity

Domain of the recurrence

Fibonacci sequence

Tower of Hanoi

Merge-sort style recurrence

Last-step counting pattern

Uniqueness / well-posedness

Generating values by hand

Worked examples

Exercises

CS connection

Common pitfalls

Checkpoint

Selected mini-solutions

Deepening notes

Base-case audit procedure

Fibonacci indexing wars

From recurrence to algorithm cost

Extra drills

Flash

Exam drill block

Mini solutions

Worked setup gallery

Synthesis

Checklist before solving (Day 55)

Tomorrow

Day 55 — Solving recurrences

Why this matters

Theory

First-order linear homogeneous

First-order linear nonhomogeneous (constant inhomogeneity)

Second-order linear homogeneous

Fibonacci closed form (Binet)

Hanoi closed form

Divide-and-conquer (unfolding lite)

Ordinary generating functions (lite)

Fibonacci GF derivation sketch

Simple coefficient extraction

Worked examples

Exercises

CS connection