How to solve below recurrence relation using subtitution method ?

Question

T(n)=T(n-3)+cn2

T(n-3)=T(n-6)+c(n-3)2

T(n-6)=T(n-9)+c(n-6)2

Continuing like this I am getting T(n)=T(n-3k)+cn2+c(n-3k)2+c(n-(3k+3))2+c(n-(3k+6))2+c(n-(3k+9))2+......

Now let k=(n-1)/3 ,I am only able to get terms like cn2+c+4c+25c +64c, with which I am unable to reach any conclusion , so how to proceed through this .

Answer 1

Please go through my solution:

I suggest ,download the image first then view it for better clarity.

Comments

I have just one confusion after u took k=n-1/3 ,Now u eradicated the term cn^2 by taking it to be c(3k+1)^2 ,Now when we are subtituting the value of k in initial terms then how come we have again introduced it , what was the problem in keeping it as it is.

---

we can write cn²  as c[n -3k +3k]² . Now put n- 3k = 1, term will become c[1+3k]^2.

And moreover we are not introducing K again....Initial condition is not given in question ,so we assumed it T(1) =  C_0.  Please check at TOP in solution given .Without initial condition ,we don't know where recursion will stop.So initial condition must be given.Now we have adjusted n-3k  = 1 in order to get the term T(1) so that we can stop our recursion after finite no of steps.

^{I hope u got it..}