How to think about solving recurrences?

Question

I am having trouble finding a closed-form solution to the following recurrence for $T(i)$, $0\le i\le n$.

$$T(0) = T(1) + 2,\quad T(n) = 0$$ and $$T(i) = {T(i+1)\over 2} + {T(i-1)\over 2} + 1,\quad 0<i<n.$$

The nearest I can come to a closed form solution is $T(i)=2{n^2}-2i^2$, which is close but not quite there.

I am frustrated because I feel like I don't have a sense for how to find solutions for more complicated recurrence relations. My professors and advice on the internet seem to consistently say, "guess and check" is the best method. That is getting me nowhere. Can anyone provide guidance on how to best to think about finding solutions to recurrences like the one above?

Answer 1

$$T(i) = {T(i+1)\over 2} + {T(i-1)\over 2}+1$$ See the pattern . $i=1$$$T(1)=T(2)/2+T(0)/2+1$$ Use $T(0)=T(1)+2$ to get $$T(1)=T(2)+4$$ ||ly get$$ T(2)=T(3)+6$$ $$T(3)=T(4)+8$$ and so on....

So, $$T(i)=T(i+1)+2(i+1)$$ $i=n-1$$$T(n-1)=T(n)+2n$$ $$T(n-1)=2n$$ $$T(n-2)=T(n-1)+2(n-1)=2n+[2n-2]=4n-2$$ $$T(n-3)=T(n-2)+2(n-2)=4n-2+[2n-4]=6n-6$$ $$T(n-4)=T(n-3)+2(n-3)=6n-6+[2n-6]=8n-12$$

Now observe the pattern for $T(n-k)$ and then put $k=n-i$, so you get $T(i)$

$$T(n-k)=2nk-k^2+k$$;$$T(i)=(n-i)(n+i+1)$$

Answer 2

OK, your recurrence is: $$ T(0) = T(1) + 2 \quad T(n) = 0 $$ and for $k \ge 1$: $$ T(k) = \frac{T(k - 1) + T(k + 1)}{2} $$ I.e., it is: $$ T(k + 2) = 2 T(k + 1) - T(k) \quad T(1) = T(0) - 2 \quad T(n) = 0 $$ Define the generating function: $$ g(z) = \sum_{k \ge 0} T(k) z^k $$ From the recurrence, multiply by $z^k$ and sum over $k \ge 0$: $$ \frac{g(z) - T(0) - T(1) z}{z^2} = 2 \frac{g(z) - T(0)}{z} - g(z) $$ This gives: $$ g(z) = \frac{T(0) - z (T(0) + 2)}{(1 - z)^2} = \frac{T(0) + 2}{1 - z} - 2 \frac{1}{(1 - z)^2} $$ Now we need: $$ (1 - z)^{-n} = \sum_{k \ge 0} (-1)^k \binom{-n}{k} z^k = \sum_{k \ge 0} \binom{k + n - 1}{n - 1} z^k $$ so we get: $$ T(k) = (T(0) + 2) - 2 \binom{k + 1}{1} = T(0) - 2 k $$ This checks out as solution. Now use $T(n) = 0$ to get: $$ \begin{align*} T(n) &= 0 = T(0) - 2 n \\ T(0) &= 2 n \end{align*} $$ So finally: $$ T(k) = 2 (n - k) $$

---

BTW, we could have noticed that: $$ g(z) = T(0) \frac{1 - z}{(1 - z)^2} - 2 \frac{z}{(1 - z)^2} = T(0) \frac{1}{1 - z} - 2 \sum_{k \ge 0} k z^k $$ thus getting the result directly.