別に漸化式を厳密に解く必要ないでしょ。
max{P(i) ; n≦i≦n+k-1}-min{P(i) ; n≦i≦n+k-1}をΔ(n)とかおくと
nが十分大きいとき、Δ(n+k)≦rΔ(n)、0 < r < 1は定数、
みたいな感じの評価が出来るはずなので
こういうことを使って示せばよい。