How do I find the closed form of a recurrence relation?

Question

I'm stuck on how to find closed forms of recurrence relations. My current problem is:

An employee joins a company in 1999 with a starting salary of $50,000. Every year this employee receives a raise of 1,000 plus 5% of the salary of the previous year.

The basic setup I have for the relation is:

A0 = 50,000 A1 = 53,500 A2 = 57,175 An+1 = 1.05An + 1000

My problem is on finding an explicit formula for the salary of the employee n years after 1999. I believe this is called the closed form. I'm stuck! Can anyone help?

Answer 1

For me, it's easier to establish a pattern from general values. Let $P_0$ be the initial salary, $P_n$ be the salary after the $n$th year, $D = 1000$ be the fixed raise, and $r=0.05$ be the raise rate.

You can then write down the first few values

$$P_1 = (1+r) P_0 + D$$

$$P_2 = (1+r) P_1 + D = (1+r)^2 P_0 + [1+(1+r)]D$$

$$P_3 = (1+r) P_2 + D = (1+r)^3 P_0 + [1+(1+r)+(1+r)^2]D$$

I hope you can see that

$$P_n = (1+r)^n P_0 + \left ( \sum_{k=0}^{n-1} (1+r)^k \right ) D$$

Evaluating the geometric sum, we get

$$P_n = (1+r)^n P_0 + \frac{(1+r)^n - 1}{r} D$$

If the employee started in 1999, then in 2013, (s)he is making $\$118,595$.

Answer 2

You have the right recurrence set up. $$A_{n+1} = 1.05 A_n + 1000 \implies \left(A_{n+1} + x \right) = 1.05 \left(A_n + x\right)$$ where we need $1.05x -x = 1000 \implies x = \dfrac{1000}{0.05} = 2 \times 10^4$. Hence, if we let $B_ n =A_n + 2 \times 10^4$, we get that $$B_{n+1} = 1.05 B_n$$ I am sure you can take it from here to get $B_n$ and thereby $A_n$.

Answer 3

Hint: $$A_2=1000 + 1.05 A_1 = 1000+ 1.05(1000 + 1.05\cdot 50000) = 1000 + 1.05\cdot 1000 + 1.05^2\cdot 50000$$

Then $$A_3= 1000 + 1.05A_2 = 1000 + 1.05\cdot 1000 + 1.05^2\cdot 1000 + 1.05^3\cdot 50000$$

Start looking for a pattern here first.