# Solving of basic recurrence relation

let us suppose we have following recurrence relation

$$T(n)=T(n-1)+1$$ where $$T_{0}=1$$

we need to find homogeneous solution and particular solution , for homogeneous solution, we have

$$T(n)-T(n-1)=0$$ so in index form $$a_n-a_{n-1}=0$$ therefore $$r-1=0$$ , from where we have $$r=1$$ and general solution will be $$a_n=\alpha*r^n$$ , because $$r=1$$ we have $$a_n=\alpha$$ now for particular solution we have $$f(n)=1$$ , that why simple take particular solution $$T_p=A$$ if we put get

$$A=A+1$$ but how to solve this equation? please help me

• any help guys?of course i can use iterated version but i need to know how to solve using characteristic equation – dato datuashvili Oct 7 '18 at 12:40

## 1 Answer

The solution to $$T(n) = T(n-1) + 1$$ is $$T(n) = n + T(0)$$.
The solution to $$T(n) = T(n-1)$$ is $$T(n) = T(0)$$.

• i know but can i find it using characteristic equation? – dato datuashvili Oct 7 '18 at 20:27
• i think that there was a misunderstanding ,, i have asked about if it is possible to solve this system using characteristic equation , homogeneous and non homogeneous techniques – dato datuashvili Oct 7 '18 at 20:53