<s>[INST] Finding Recurrence relations for combinatorics problems After you graduate you accept a job that promises a starting salary of $40,000$ and a raise at the end of each year equal to $5\%$ of your current salary plus $1000$. For example, your raise at the end of the first year is $3000$. Let $S_n$ be your salary after $n$ years, so that $S_0 = 40,000$.
A- Find a recurrence relation. 
B- Determine how much you will be making after $2$ years, after $5$ years, after $10$ years. 
I did part A.  I don't know if I did it correctly, so it's $S_{n+1} = S_n \cdot 1.05+1000$ with $S_0=40,000$.
 [/INST] The recurrence relation 
\begin{align*}
S_0 & = 40,000\\
S_{n + 1} & = S_n \cdot 1.05 + 1000
\end{align*}
that you stated is correct.
Let's look at the first few terms of the sequence.
\begin{align*}
S_1 & = S_0 \cdot 1.05 + 1000\\
    & = 40,000 \cdot 1.05 + 1000\\
S_2 & = S_1 \cdot 1.05 + 1000\\
    & = (40,000 \cdot 1.05 + 1000) \cdot 1.05 + 1000\\
    & = 40,000 \cdot 1.05^2 + 1000 \cdot 1.05 + 1000\\
S_3 & = S_2 \cdot 1.05 + 1000\\
    & = (40,000 \cdot 1.05^2 + 1000 \cdot 1.05 + 1000) \cdot 1.05 + 1000\\
    & = 40,000 \cdot 1.05^3 + 1000 \cdot 1.05^2 + 1000 \cdot 1.05 + 1000\\
    & = 40,000 \cdot 1.05^3 + 1000(1.05^2 + 1.05 + 1)
\end{align*}
If we use the geometric series formula 
$$\sum_{k = 0}^{n} r^{k - 1} = 1 + r + r^2 + \cdots r^{n - 1} = \frac{1 - r^n}{1 - r}$$
we can express $S_3$ in the form 
$$S_3 = 40,000 \cdot 1.05^3 + 1000 \cdot \frac{1 - 1.05^3}{1 - 1.05}$$
Can you find a formula for $S_n$? 
</s>