-1

Using generating function determine sequence $u_n$: $$u_0 = 1, \ u_1 = 0, u_{n+2} - 4u_{n+1} + 4u_n =0 $$ I am asking for advices. Thanks in advance.

user180834
  • 1,453

2 Answers2

2

Do you know the concept of generating functions?

Just solve the equation for $ u_{n+2}$. Then you are ready to go.

Edit:

My proceeding would have been to define $$ A(x) = \sum\limits_{n = 0}^\infty u_n x^n $$

Now you set in the starting values of $ u_n $ and write:

$$ A(x) = u_o + u_1 \cdot x + \sum\limits_{n = 2}^\infty (4u_{n-1} - 4u_{n-2})x^n $$

Now you shift the index of the series and get

$$ A(x) = 1 - 4x^2A(x) + 4xA(x) $$

You can now solve for $ A(x) $ and arrange this result as power series. Simply look at the coefficients of your new power series and you get $ u_n $.

kummerer94
  • 356
  • Well, I learned it the way to write $ u_{n+2} = 4u_{n+1} - 4u_n $ and arrange a power series to later solve for it.

    It is the same type of proceeding as enigne did but enigne simply shortened it.

     – kummerer94 Jan 01 '15 at 12:41
  • Really good edit you did there, this is much, much better. +1 :). – Lord_Farin Jan 01 '15 at 18:00
  • Thank you very much, I should have written it this way the first time. :) Shouldn't write posts on the iPad. :D – kummerer94 Jan 01 '15 at 21:05
0

The way is first to solve the generating function $x^2-4x+4=0$ and get the solutions $x_1=x_2=2$. So, the general form of the sequence is $u_n=\alpha\cdot2^n+\beta\cdot n 2^n$. By the initial settings, $u_0=1,\,u_1=0$, we get $\alpha=1,\,\beta=-1$. Then, $u_n=(1-n)2^n$.

enigne
  • 813