When a counting recurrence's characteristic polynomial has a repeated root r, why is A*r^n + B*r^n not a general solution?

## The dimension argument A linear homogeneous recurrence of order `k` with constant coefficients has a solution space of dimension exactly `k`: the first `k` values may be chosen freely and everything after them is forced. So a general solution must carry **k independent arbitrary constants**, and a candidate form that carries fewer is not general, however many letters appear in it. With distinct roots `r1, ..., rk`, the geometric sequences `ri^n` are independent and the count works out. When two roots coincide you have only one distinct geometric sequence, and writing it twice is arithmetic theatre: `A*r^n + B*r^n = (A+B)*r^n` That is one parameter wearing two names. Given two independent initial conditions, it will generally fail to satisfy both — the symptom in an interview is a candidate producing two equations in what is really one unknown and getting a contradiction. ## Why n*r^n is the missing solution The repair is to multiply by `n`, which is not a constant factor, so `n*r^n` is genuinely independent of `r^n`. It also genuinely satisfies the recurrence. Take the order-2 example `f(n) = 4f(n-1) - 4f(n-2)`, whose characteristic polynomial is `r^2 - 4r + 4 = (r-2)^2` with the double root `r = 2`. Substituting `f(n) = n*2^n`: `4*(n-1)*2^(n-1) - 4*(n-2)*2^(n-2) = 2*(n-1)*2^n - (n-2)*2^n = (2n - 2 - n + 2)*2^n = n*2^n` It checks out exactly. The general rule is that a root of **multiplicity m** contributes the `m` independent solutions `r^n, n*r^n, n^2*r^n, ..., n^(m-1)*r^n`, so the total number of basis solutions is still the order of the recurrence — multiplicities are counted, never dropped. ## A worked instance end to end With `f(0) = 1` and `f(1) = 6`, the form `(A + B*n)*2^n` gives `A = 1` from `n = 0`, and `(1 + B)*2 = 6` so `B = 2`. Now compare the two routes: | n | from the recurrence 4f(n-1) - 4f(n-2) | from (1 + 2n)*2^n | |---|---|---| | 0 | — (given) | 1 | | 1 | — (given) | 6 | | 2 | 4*6 - 4*1 = 20 | 5*4 = 20 | | 3 | 4*20 - 4*6 = 56 | 7*8 = 56 | | 4 | 4*56 - 4*20 = 144 | 9*16 = 144 | They agree, which is the check worth doing aloud before trusting any closed form. ## What the extra factor does to growth - The **base is unchanged**: the exponential part is still `r^n`. The `n` factor is polynomial, not exponential. - The growth is therefore `n*r^n` in order of magnitude — strictly bigger than `r^n`, but by a factor that grows only linearly. - The ratio of consecutive terms still tends to `r`, but approaches it from one side rather than sitting on it, so a naive fit of a pure geometric to a few values will mis-estimate the constant. - Reporting such a sequence as "exponential with base r" is right about the base and understates the total by a linear factor — worth saying explicitly when the number is a capacity claim. ## How to spot the case before you are stuck 1. For an order-2 recurrence `f(n) = p*f(n-1) + q*f(n-2)`, the polynomial is `r^2 - p*r - q`, and the root repeats exactly when its discriminant `p^2 + 4q` is zero. 2. More generally, a polynomial has a repeated root precisely when it shares a factor with its own derivative, so a non-trivial greatest common divisor of the two is the general test. 3. Empirically: if the values do not fit `A*r1^n + B*r2^n` for any constants, and the recurrence is genuinely linear with constant coefficients, suspect a repeated root rather than an error in the data. ## What is actually being checked This is a differentiator rather than a screening question. The interviewer is watching whether you understand the **structure** of the solution — that the answer is a basis for a `k`-dimensional space, not a formula to reproduce. A candidate who knows why two copies of one solution is still one solution will re-derive the `n*r^n` fix under pressure; a candidate who memorised the distinct-roots formula will not.