Why Do We Divide by the Lowest Power in a Recurrence Relation?

When solving the Gambler’s Ruin recurrence

we assume a trial solution of the form

which gives

At this stage, we divide by the lowest power, , because it is the greatest common factor of all terms.

Using the exponent rule

we obtain

which can be rewritten as

This equation is called the characteristic equation.

Why Not Divide by r^i?

We can divide by

instead, giving

Multiplying by again produces

which is the same result.

Therefore, both methods are correct.

The Key Insight

For powers of the same variable, the greatest common factor is obtained by taking the smallest exponent.

For example,

have greatest common factor

Similarly,

have greatest common factor

Dividing by the greatest common factor usually produces the cleanest algebra and avoids unnecessary fractions.

Key Takeaway

When solving linear recurrences, dividing by the lowest common power is often preferred because it removes the greatest common factor and leads directly to a simpler characteristic equation.