# recurrence - Iteration method T(n)=T(n-a)+n [duplicate]

I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1.

So I started to iterate T(n)=T(n-a)+n =T(((n-a)+n)-a)+n =T(3n-3a)+n =T(((3n-3a)+n)-a)+n =T(4n-4a)+n

this brings me to the Basic: T(kn-ka)+n.

Is it right ? I am not sure how to solve such Terms with a constant ? thank you for your help !!

## marked as duplicate by D.W.♦, Yuval Filmus, FrankW, David Richerby, Luke MathiesonNov 14 '14 at 4:04

Hint: Let's solve the case $a = 1$; I'll leave the generalization to you: \begin{align*} T(n) &= n + T(n-1) \\ &= n + (n-1) + T(n-2) \\ &= n + (n-1) + (n-2) + T(n-3) \\ &= \cdots \\ &= n + (n-1) + (n-2) + \cdots + (1) + T(0) \\ &= \frac{n(n+1)}{2} + T(0). \end{align*} In the general case, if $n = ma$ then you'll get $am(m+1)/2 + T(0) \approx n^2/(2a) + T(0)$.

• Hi! First of all thanks for your Response! :) I solved the case when a = 1 but due to the reason that a can be 2, 3 ... I don´t think that it is right ? My solution for the case that a = 1 Looks like: – bee23 Nov 12 '14 at 21:50
• T(n) = T(n-1) + n / (n-1) It step T(n-1) = T(n-2) + (n-1) / (n-2) It step T(n-2) = T(n-3) + (n-2) --> T(n) = T(n-2) + (n-1) + n T(n) = T(n-3) + (n-2) + (n-1) + n The base = T(k-a) + kn - 1/2(k(k-1)) – bee23 Nov 12 '14 at 21:57
• The same method works for any constant $a$. Keep trying and you'll get my formula eventually. You can even get a formula when $n$ is not a multiple of $a$. – Yuval Filmus Nov 12 '14 at 22:00

Okay :) let´s try again.

T(n) = T(n – a) + n / a=1

1. T(n) = T(n-1) + n /Iterationstep
2. T(n-1) = T(n-2) + (n-1) / (n-2) Iterationstep
3. T(n-2) = T(n-3) + (n-2)

-> T(n-1), T(n-2) in T(n):

T(n) = T(n-2) + (n-1) + n

T(n) = T(n-3) + (n-2) + (n-1) + n

Base= T(k-a) + kn – ½(k(k-1))

n - k =1 --> T(1)

T(n) = T(1) + (n-1)n - (n-1)(n-2)/2

(n(n+1))/2= Ω (n2)

So this is my solution for a = 1 I think/hope it is right ?!