Fibonacci Sequence help...again

Question

I'm back again stuck on another problem:

Solve the recurrence relation:

(1) S(1)=1

(2) S(n) =nS(n−1) + n! for n≥2

Here's what I have done so far:

Expand:

S(n) = nS(n-1) + n!

S(n-1) = nS(n-2)+n!

S(n) = n [nS(n-2) + n!] + n! => n^2[S(n-2) + (n^2)!] + n!

S(n-2) = nS(n-3)+n!

S(n) = n^2[nS(n-3)+n!] + (n^2)! + n! => n^3[S(n-3) + (n^3)!] + (n^2)! + n!

So....

Guess:

S(n) = n^(k) x S(n-k) + n^(k)! + n^(k-1) + k!

I tried checking it by plugging in numbers (of course after plugging in "n-1" for (k) but they did not equal each other. I know I'm doing this wrong, but I'm not sure if it's cause of my algebra or I'm just doing everything completely wrong. Any feedback would be greatly appreciated by you guys.

Answer 1

Hint:

$$ \begin{align} S_n & = nS_{n-1} + n! \\ & = n\big((n-1)S_{n-2}+(n-1)!\big) + n! = n(n-1)S_{n-2} + 2 n! \\ & = n(n-1)\big((n-2)S_{n-3} + (n-2)!\big) = n(n-1)(n-2)S_{n-3} + 3 n! \\ & = \cdots \end{align} $$

Answer 2

Let $T(n)=\frac{S(n)}{n!}$, we get nicely $$T(n)=T(n-1) + 1$$ for $n\ge 2$.

And $T(1)=1$, so $T(n)=n$, and $$S(n)=n\cdot n!$$

Answer 3

Honestly, that's not how I would start a problem like this - when you start doing algebra without a goal in mind, you just end up with variable salad.

Start by examining the first few examples and comparing them with sequences that seem related. The first four are $S(1) = 1$, $S(2) = 4$, $S(3) = 18$, $S(4) = 96$. Some possibly related sequences are $n$, $n^n$, and $n!$. The first four terms of these sequences are $1, 2, 3, 4$; $1, 4, 27, 256$; and $1, 2, 6, 24$ respectively. There doesn't seem to be an obvious relationship between $n$ and $S(n)$, nor between $n^n$ and $S(n)$; but $S(n)$ is always a multiple of $n!$. Can you see which multiple of $n!$ it is? That will give you a hypothesis for $S(n)$.

Now that you have a goal in mind, use algebra to prove it - verify that your hypothesis obeys both the initial condition and the recursive step.