Use the method of "changing variables" to solve the following recurrence:

Question

$T(n) = 2\cdot T(n-2) + n$

I tried doing this, but I don't know how to continue from here. I think it doesn't work and is not correct.

Please help, thanks in advance!

Answer 1

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{n = 2}^{\infty}\mrm{T}\pars{n}z^{n} & = 2\sum_{n = 2}^{\infty}\mrm{T}\pars{n - 2}z^{n} + \sum_{n = 2}^{\infty}n\,z^{n} \\[5mm] -\,\mrm{T}\pars{0} - \mrm{T}\pars{1}z + \sum_{n = 0}^{\infty}\mrm{T}\pars{n}z^{n} & = 2z^{2}\sum_{n = 0}^{\infty}\mrm{T}\pars{n}z^{n} + {\pars{2 - z}z^{2} \over \pars{1 - z}^{2}} \end{align}

Lets $\ds{\mc{T}\pars{z} \equiv\sum_{n = 0}^{\infty}\mrm{T}\pars{n}z^{n}}$ such that $\ds{\mrm{T}\pars{n} = \bracks{z^{n}}\mc{T}\pars{z}}$.

Then, \begin{align} \mc{T}\pars{z} & = {\mrm{T}\pars{0} + \mrm{T}\pars{1}z + \pars{2 - z}z^{2}/\pars{1 - z}^{2} \over 1 - 2z^{2}} \\[5mm] & = -\,{1 \over \pars{1 - z}^{2}} - {3 \over 1 - z} + {\mrm{T}\pars{0} + \mrm{T}\pars{1}z + 4 + 5z \over 1 - 2z^{2}} \\[5mm] & = -\sum_{n = 0}^{\infty}{-2 \choose n}\pars{-1}^{n}z^{n} - 3\sum_{n = 0}^{\infty}z^{n} + \braces{\vphantom{\large A}\mrm{T}\pars{0} + 4 + \bracks{\mrm{T}\pars{1} + 5}z} \sum_{n = 0}^{\infty}2^{n}z^{2n} \\[5mm] & = -\sum_{n = 0}^{\infty}\pars{n + 4}z^{n} + \sum_{n = 0}^{\infty}\bracks{\mrm{T}\pars{0} + 4}2^{n}z^{2n} + \sum_{n = 0}^{\infty}\bracks{\mrm{T}\pars{1} + 5}2^{n}z^{2n + 1} \\[1cm] & = \sum_{n = 0}^{\infty}\braces{\vphantom{\large A}\bracks{\mrm{T}\pars{0} + 4}\pars{\root{2}}^{2n} - 2n - 4}z^{2n} \\[2mm] & + \sum_{n = 0}^{\infty}\braces{\vphantom{\large A} {\root{2} \over 2}\bracks{\mrm{T}\pars{1} + 5}\pars{\root{2}}^{2n + 1} - \pars{2n + 1} - 4}z^{2n + 1} \end{align}

---

$$ \bbx{\mrm{T}\pars{n} = \left\{\begin{array}{lcl} \ds{\bracks{\mrm{T}\pars{0} + 4}2^{n/2} - n - 4} & \mbox{if} & \ds{n}\ \mbox{is}\ even \\[2mm] \ds{\bracks{\mrm{T}\pars{1} + 5}2^{\pars{n - 1}/2} - n - 4} & \mbox{if} & \ds{n}\ \mbox{is}\ odd \end{array}\right.} $$

Answer 2

Let $f(x)=T_0+T_1x+T_2x^2+....+T_nx^n+...$. Thus, $x^2f=T_0x^2+T_1x^3+T_2x^4+...+T_{n-2}x^n+....$. Also, note that $\frac{x}{(1-x)^2}=x+2x^2+3x^3+...nx^n+...$

Thus, $$f-2x^2f-\frac{x}{(1-x)^2}=T_0+(T_1-1)x+(T_2-2T_0-2)x^2+...+(T_n-2T_{n-2}-n)x^n+...$$ $$=T_0+(T_1-1)x$$

Thus, $$f=\frac{T_0}{1-2x^2}+\frac{x}{(1-2x^2)(1-x)^2}+\frac{(T_1-1)x}{1-2x^2}$$

Now, $\frac{x}{(1-2x^2)(1-x)^2}= \frac{3}{\left(x-1 \right)}+{\frac {-6\,x-4}{2\,{x}^{2}-1}}- \frac{1}{\left( x-1 \right) ^{2}}$

Thus atlast we have: $$f=\frac{T_0+4}{1-2x^2}+\frac{(T_1+5)x}{1-2x^2}+\frac{3}{x-1}-\frac{1}{(x-1)^2}$$ All the above functions are closed forms of well knows geometric series, from which we can find the coefficient of $x^n$ which gives us $T_n$(From the definition of $f$ in the beginning of the answer)

Answer 3

Hint (using "change of variables"):

$$ \begin{align} T(n) = 2\cdot T(n-2) + n \;\;&\iff\;\; T(n)+n=2\cdot \big(T(n-2)+n-2\big) +4 \\ &\iff\;\; T(n)+n+4=2\cdot \big(T(n-2)+n-2+4\big) \end{align} $$

Let $\,S(n) = T(n)+n+4\,$, then $\,S(n) = 2 \cdot S(n-2)= 2^2 \cdot S(n-4) = 2^3 \cdot S(n-6)= \ldots\,$