I’m working on the following recurrence relation using the iteration technique:

????(????) = ????(???? − 1) + ????????

Here is my process using the technique and deriving a general solution:
my work with solution in red

My question comes down to the summation at the end. I do not understand why the correct summation starts at i = k + 1 and culminates at n when in my iterations there are really k terms (k – 1 terms when i begins at 0), each of the form n – i.

I don’t see recurrence relations like this a lot, so I would like to know the logic that led to the correct solution (the key doesn’t contain this info).