exact-closed form solutions of recurrences

Question

How can I find the exact-closed form solution of this recurrence?

$$f(n) = (1/2)f(n-2) + n/2,$$ where n is even, $f(0)=1$

My answer:

I try to guess a solution by unwinding the formula for f(n)

$f(n) = (1/2)f(n-2) + n/2$$

$= (1/2) ((1/2)f(n-4) + ((n-2)/2) )+n/2$

$=(1/2)^2f(n-4)+n/2^2+n/2 -2/2^2$

$=(1/2)^3f(n-6)+n/2^3+n/2^2+n/2 -2/2^2-4/2^3$

$=(1/2)^4f(n-8)+n/2^4+n/2^3+n/2^2+n/2 -2/2^2-4/2^3-6/2^4$

Continuing in this manner suggest the sum:

$f(n)=1/2^{(n/2)}f(0)+n(1/2^{n/2}+1/2^{(n/2)-1}+...+1/2)-(2/2^2+4/2^3+6/2^4+...)$

$f(n)=1/2^{(n/2)}+n(1-(1/2)^{n/2})-(2/2^2+4/2^3+6/2^4+...)$

How could I solve the expression $(2/2^2+4/2^3+6/2^4+...)$ and find the exact-closed form solution of this recurrence?

Answer 1

Hint: Look for a solution in the form $$f(n) = A r^n + B n + C$$

Answer 2

Hint

Let $g(m)=f(m)+a_0+a_1m+\cdots$

$n=2f(n)-f(n-2)=2g(n)-g(n-2)+a_0(2-1)+a_1\{2n-(n-2)\}$

Set $a_i=0$ for $i\ge2$ and $a_1=1$ and $a_0+2a_1=0$

so that $g(n)=\dfrac{g(n-2)}2=\dfrac{g(n-2r)}{2^r}$

Set $2r=n$

Answer 3

Your direct question is about the sum $$ \eqalign{ & 2/2^{\,2} + 4/2^{\,3} + 6/2^{\,4} + \cdots = \cr & = 1 \cdot \left( {{1 \over 2}} \right)^{\,1} + 2 \cdot \left( {{1 \over 2}} \right)^{\,2} + 3 \cdot \left( {{1 \over 2}} \right)^{\,3} + \cdots = \cr & = \sum\limits_{1\, \le \,k} k \left( {{1 \over 2}} \right)^{\,k} \cr} $$

Since $$ \eqalign{ & \sum\limits_{0\, \le \,\left( {\,1\, \le } \right)\,k} {k\,z^{\,k} } = z\sum\limits_{0\, \le \,k} {k\,z^{\,k - 1} } = z{d \over {dz}}\sum\limits_{0\, \le \,k} {z^{\,k} } = \cr & = z{d \over {dz}}{1 \over {\left( {1 - z} \right)}} = {z \over {\left( {1 - z} \right)^{\,2} }} \cr} $$ then the sum equals $$ \sum\limits_{1\, \le \,k} k \left( {{1 \over 2}} \right)^{\,k} = 2 $$