It's a simple math problem, i think.
If we write Z_n = S_n + P_n = n^k + S_n - 1 + nⁿ + P_n - 1
So we can write Z_n + Z_n - 1 = n^k + nⁿ + 2 * Z_n - 1
As a result, we can write Z_n + Z_n - 1 - 2 * Z_n - 2 = nⁿ + n^k + 2 * (n - 1)^n - 1 + 2 * (n - 1)^k.
This can be calculated in logarithmic time with fast exponentiation.

I solved it with the following thought process (In my opinion, giving thoughts is more important than the solution itself).
First notice the coefficients Z_n + Z_n - 1 - 2Z_n - 2)
1 + 1 - 2 = 0
That looks suspicious!

Then we take a look at S_n and P_n.
Hmm ... Have you noticed something interesting?
If not, write down S₃ S₄ S₅ and so on
and you'll notice:
S_n = S_n - 1 + n^k = S_n - 2 + (n - 1)^k + n^k
Similarly with P_n
P_n = P_n - 1 + nⁿ = P_n - 2 + (n - 1)^n - 1 + nⁿ

Then we substitute S_n, S_n - 1, P_n, P_n - 1 in the original sequence,
we get Z_n + Z_n - 1 - 2Z_n - 2 = 2(n - 1)^k + n^k + 2(n - 1)^n - 1 + nⁿ

which leads to the solution