Use induction to solve the recurrence relation..!!

Question

I don't know how to start this problem. I just need someone to show me the first couple steps of doing the induction for this relation. c is a constant.

$T(n) = T(n - 4) + c\cdot n^{1/4}$

Thanks for the help..!!

Answer 1

It looks like this splits into 4 completely independent sequences. Each of them only depends on its own initialization (first term).

In this sense, this is a recurrence realtion of first order.

For induction, you first need a proposed solution, otherwise you don't have anything to prove. The solution for each subsequence is simply the sum $T(4n+m)=T(m)+c\sum_{k=0}^n (4k+m)^{1/4}$ where $m=0,1,2,4$ is the subsequence you are observing.

The sum itself doesn't look like something you could simplify.

Answer 2

It would appear that $$T(4n)=c\sum_{k=0}^{{n}}{(4k)^{{1\over 4}}}$$ for $n$ divisible by 4, and similarly for other types of $n$ (there are four cases to consider). Assume this formula is true for some n, and show (using the recurrence formula) that it will also be true for the next $n+1$. There isn't really a base case to worry about, as you didn't specify and initial conditions.