1

I want to solve the following recurrence, for any parameter $x>0$:

$ a[i]= \frac{1}{x} a[i+1]+ (1- \frac{1}{x}) a[i-1]$ for $i \in \{1,...,n-1\}$

$a[0]= 0, a[n]=1$.

i.e. find a closed form for $a[i]$ for any $i \in \{0,...,n\}$

I know that the solution must be $\frac{(x-1)^i-1}{(x-1)^n-1}$,

but I want to find this solution myself. My approach was using the generating function as here, however, I am not sure how to deal with the boundary conditions giving ``on both sides'' i.e. a[0] and a[n].

How can I find the closed solution (using the generating function technique)?

black
  • 259
  • Hint: the recurrence in standard form is $,a_{k+1}=xa_k-(x-1)a_{k-1},$, with characteristic polynomial $,t^2-xt+x-1 = (t-1)\left(t-(x-1)\right),$, so $,a_k = \lambda \cdot 1^k + \mu \cdot (x-1)^k,$. Use the two conditions for $,k=0,$ and $,k=n,$ to determine $,\lambda, \mu,$. – dxiv May 02 '22 at 01:33

0 Answers0