I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$.
My Try: For $a=1$ this is just the Fibonacci sequence and I have $$u_{N}=\frac{\alpha^{N}-\beta^{N}}{\alpha -\beta}$$ where $\displaystyle \alpha=\frac{1+\sqrt{5}}{2},\quad \beta=1-\alpha$.
For $a\in (0,1)$, I thought about finding the formal power series of $u_n$, but when I try to find that out I get the following: $$x^{-2}(U(x)-x-1)=x^{-1}(U(x)-1)+a^{N-1}U\left(\frac{x}{a}\right)\\\Rightarrow U(x)=\frac{1+x^2a^{N-1}U\left(\frac{x}{a}\right)}{1-x} $$ Is it possible to find $U(x)$ from here? If not, is there some other method by which I can get $u_N$? Thank you.
We have $\pmatrix{u_{n+1}\cr u_n\cr} = \pmatrix{1 & a^{N-n}\cr 1 & 0\cr} \pmatrix{u_n\cr u_{n-1}\cr}$, and thus $$ \pmatrix{u_{N+1}\cr u_N\cr} = \pmatrix{1 & 1\cr 1 & 0\cr} \pmatrix{1 & a\cr 1 & 0\cr} \ldots \pmatrix{1 & a^{N-1}\cr 1 & 0\cr} \pmatrix{u_1\cr u_0\cr}$$ If $$P_k = \pmatrix{1 & 1\cr 1 & 0\cr} \pmatrix{1 & a\cr 1 & 0\cr} \ldots \pmatrix{1 & a^{k}\cr 1 & 0\cr}$$ we have $$ P_k = \pmatrix{A_k(a) & A_{k-1}(a) a^k\cr B_k(a) & B_{k-1}(a) a^k\cr}$$ where both $A_k(a)$ and $B_k(a)$ satisfy the recursion $$ v_{k+1} = v_k + v_{k-1} a^k$$ with different initial conditions: $A_0(a) = 1, A_1(a) = 2$ while $B_0(a) = 1, B_1(a) = 1$. $A_k$ and $B_k$ will be polynomials in $a$ of degree $k^2/4$ if $k$ is even, $(k^2-1)/4$ if $k$ is odd. Note that the coefficients of $a^j$ in $A_k(a)$ and $B_k(a)$ are constant for $k > j$.
I doubt that there is a closed form.