Question

$f$ is a function for which $f(1)=1$ and $f(x) = 2x + f(x-1)$ for each natural number $x \geq 2$. Find $f(31)$.

• A. 869
• B. 929
• C. 951
• D. 991
• E. None of the above

Hint:

For recurrence relations like $f(x)=f(x-1)+g(x)$, expand the terms to convert into a summation. Then apply formulae for sums of natural numbers to find the closed form.

Answer 1

The Correct Option is D

Step 1: Write the recurrence relation.
We are given: \[ f(1) = 1, \qquad f(x) = 2x + f(x-1), \ \text{for } x \geq 2. \] Step 2: Expand the recurrence for first few terms.
\begin{align*} f(2) &= 2..... 2 + f(1) = 4 + 1 = 5,
f(3) &= 2..... 3 + f(2) = 6 + 5 = 11,
f(4) &= 2..... 4 + f(3) = 8 + 11 = 19,
f(5) &= 2..... 5 + f(4) = 10 + 19 = 29. \end{align*} So the sequence goes: $f(1)=1, f(2)=5, f(3)=11, f(4)=19, f(5)=29,\dots$ Step 3: Generalize the recurrence.
We can unfold the recurrence: \begin{align*} f(x) &= f(x-1) + 2x,
&= f(x-2) + 2(x-1) + 2x,
&= f(x-3) + 2(x-2) + 2(x-1) + 2x,
& \;\vdots
&= f(1) + 2..... 2 + 2..... 3 + .....s + 2x. \end{align*} Since $f(1)=1$, we get \[ f(x) = 1 + 2\sum_{k=2}^{x} k. \] Step 4: Simplify the summation.
\begin{align*} \sum_{k=2}^{x} k &= \left(\sum_{k=1}^{x} k\right) - 1
&= \frac{x(x+1)}{2} - 1. \end{align*} So, \begin{align*} f(x) &= 1 + 2\left(\frac{x(x+1)}{2} - 1\right)
&= 1 + (x(x+1) - 2)
&= x^2 + x - 1. \end{align*} Step 5: Compute $f(31)$.
\begin{align*} f(31) &= 31^2 + 31 - 1
&= 961 + 30
&= 991. \end{align*} \fbox{\parbox{0.97\linewidth}{ \centering $f(31) = \boxed{991}$ }}