Combinatorics

Four techniques, one worked instance each

Strong induction, pigeonhole, a recurrence solved two ways, and a structural induction on graphs.

1. Strong induction

Claim. Every integer n≥12 can be written as 4*a+5*b with a,b≥0

Base cases. 12=4⋅3 13=4⋅2+5 14=4+5⋅2 15=5⋅3

Step. Let n≥16 and assume the claim for every integer from 12 up to n−1 Then n−4≥12 so n−4=4*a+5*b for some a,b≥0 and

n=4*(a+1)+5*b

By strong induction the claim holds for all n≥12

Why four base cases and not one. The step reaches back exactly 4, so the induction needs 4 consecutive starting values before it can run. With one base case there is no way to get from 12 to 13. And 12 is sharp: 11=4*a+5*b has no solution, nor do 1,2,3,6,7.

2. Pigeonhole

Claim. Choose any n+1 numbers from {1,2,…,2*n} Two of them are such that one divides the other.

Proof. Every positive integer factors uniquely as 2^k*m with m odd. For a number in {1,…,2*n} the odd part m lies in {1,3,5,…,2*n−1} and there are exactly n such values.

Pick n+1 numbers. Their odd parts are n+1 values drawn from a set of size n so two of the chosen numbers share an odd part:

x=2^j*m,y=2^k*m,j<k

Then y=2^(k−j)*x so x|y

Sharp. Taking {n+1,n+2,…,2*n} gives n numbers with no divisibility among them, since 2*(n+1)>2*n So n+1 is the smallest size that forces it.

3. A recurrence, two ways

Claim. Let (a_n) be the number of binary strings of length n with no two consecutive 1. Then (a_n)=(F_n+2) where (F_1)=(F_2)=1

The recurrence. Split on the first character. A valid string either starts 0 followed by any valid string of length n−1 or starts 10 followed by any valid string of length n−2

(a_n)=(a_n−1)+(a_n−2),(a_1)=2,(a_2)=3

Listing confirms: n=1 gives 0,1; n=2gives 00,01,10; n=3gives 000,001,010,100,101, so (a_3)=5.

Same recurrence as Fibonacci with the index shifted, and (a_1)=2=(F_3) (a_2)=3=(F_4) so (a_n)=(F_n+2)

By generating function. With A(x)=(∑_n≥0^)((a_n))*x^n and (a_0)=1

A(x)=(1+x)/(1−x−x^2)

The denominator's roots are −1/φ and φ where φ=(1+√(,5))/2, giving

(a_n)∼(φ^(n+2))/√(,5)

So the count grows like φ^n≈1.618^n rather than 2^n forbidding one pattern of length two costs the alphabet roughly 19% of its effective size.

4. Structural induction

Claim. Every tree on n vertices has exactly n−1 edges.

Lemma. Every finite tree with at least 2 vertices has a vertex of degree 1.

Proof of lemma. Take a longest path (v_0)*(v_1)⋯(v_k) in the tree, which exists because the tree is finite. If (v_0) had a neighbour other than (v_1) that neighbour is either off the path, which extends it and contradicts maximality, or on the path, which creates a cycle and contradicts acyclicity. So deg*(v_0)=1.

Induction on n. For n=1 there are no edges and n−1=0

Let T be a tree on n≥2 vertices. By the lemma it has a leaf v. Deleting v and its single edge leaves a graph on n−1 vertices that is still connected — no path through v could have used it as anything but an endpoint — and still acyclic. So T−v is a tree, and by the inductive hypothesis it has n−2 edges. Restoring v and its edge gives n−1.

The lemma is the whole proof. Without it there's no vertex you're entitled to delete, and induction on graphs generally fails at exactly that point: deleting an arbitrary vertex need not leave an object of the same kind.