A recurrence is any recursively defined function f with domain ℕ that computes numbers. To solve a recurrence f we must find an expression for the general term f(n) that is not recursive. In a simple recurrence, f only appears once on the right side of the general equation for f(n). What method(s) should we use to solve a simple recurrence? Select all that apply.

Question

A recurrence is any recursively defined function f with domain  ℕ  that computes numbers. To solve a recurrence f we must find an expression for the general term f(n) that is not recursive. In a simple recurrence, f only appears once on the right side of the general equation for f(n). What method(s) should we use to solve a simple recurrence? Select all that apply.

Answer

Cancellation, where we start with the general equation for f(n), and then write the equation for the f that is on the right side of the f(n) equation. We continue this process until a pattern emerges. Then we add up all the equations and cancel equivalent terms on the right/left to get a non-recursive definition for f(n).

Answer

Substitution, where we start with the definition for f(n) and keep substituting for occurrences of f on the right side of the equation until we discover a pattern. Once we discover the pattern, we can skip ahead and replace f(0), resulting in a non-recursive definition for f(n).

Answer

Ask Yoda.

Answer

Use a generating function, which stems from the simple idea of equating the coefficients of two polynomials.

Crowdly

A recurrence is any recursively defined function f with domain ℕ that computes...

Want instant access to all verified answers on online.clackamas.edu?