Master Method and use cases

Question

$T(n)=T(n-2)+n^{2}$ and $T(n)=4T(n-2)+n^{2}$

Master method to solve these two equations? I know I can use the other cases where $a$ and $b > 0$ but since $T(n-2)$ do I assume $b$ is $1$?

Answer 1

You can use the generating function to solve this problem. Generally, you can work on this problem: $T(n)=bT(n-2)+n^2$. (Letting $b=1$, you get the first and letting $b=4$, you get the second). In fact, let $f(x)=\sum_{n=0}^\infty T(n)x^n$. Then \begin{eqnarray*} f(x)&=&\sum_{n=0}^\infty T(n)x^n\\ &=&T(0)+T(1)x+\sum_{n=2}^\infty T(n)x^n\\ &=&T(0)+T(1)x+\sum_{n=0}^\infty T(n+2)x^{n+2}\\ &=&T(0)+T(1)x+\sum_{n=0}^\infty (bT(n)+(n+2)^2)x^{n+2}\\ &=&T(0)+T(1)x+bx^2f(x)+\sum_{n=0}^\infty (n+2)^2x^{n+2}. \end{eqnarray*} Since \begin{eqnarray*} \sum_{n=0}^\infty (n+2)^2x^{n+2}\\ &=&x(\sum_{n=0}^\infty (n+2)x^{n+2})'\\ &=&x(x+x\sum_{n=1}^\infty nx^{n-1})'\\ &=&x(x+x\frac{1}{(1-x)^2})'. \end{eqnarray*} From this, it is easy to get $f(z)$. By Taylor expansion, one can $T(n)$. For I omit the detail.