<s>[INST] An expression for $U_{h,0}$ given $U_{n,k}=\frac{c^n}{c^n-1}(U_{n-1,k+1})-\frac{1}{c^n-1}(U_{n-1,k})$ Let $c\in\mathbb{R}\setminus\{ 1\}$, $c>0$.
Let $U_i = \left\lbrace U_{i, 0}, U_{i, 1}, \dots \right\rbrace$, $U_i\in\mathbb{R}^\mathbb{N}$.
We know that $U_{n+1,k}=\frac{c^{n+1}}{c^{n+1}-1}U_{n,k+1}-\frac{1}{c^{n+1}-1}U_{n,k}$.
(As @TedShifrin pointed out, it can also be written $U_{n+1,k}=U_{n,k+1}+\frac{1}{c^{n+1}-1}\left(U_{n,k+1}-U_{n,k}\right)$)
(obviously it implies that if $\lvert U_k \rvert=n$ then $\lvert U_{k+1}\rvert=n-1$ etc)
Here is what I conjectured:
$$\forall h\in\mathbb{N}, 
U_{h,0}=\sum\limits_{p=0}^h\frac{c^{\frac{p^2+p}{2}}}{\left(\prod\limits_{i=1}^p\left(c^i-1\right)\right)\prod\limits_{i=1}^{h-p}\left(1-c^i\right)}U_{0,p}$$
I tested it for some values ($0,1,3,4$) and it seemed to work.
Mathematica also verified it up to at least 10.
What do you think? If it IS true, how can I prove it?

Example with $c=4$, $h=2$ :
$U_{1,0}=\frac{4}{3}U_{0,1}-\frac{1}{3}U_{0,0}$, $U_{1,1}=\frac{4}{3}U_{0,2}-\frac{1}{3}U_{0,1}$
$U_{2,0}=\frac{16}{15}U_{1,1}-\frac{1}{15}U_{1,0}$
Therefore $U_{2,0}=\frac{16}{15}\left(\frac{4}{3}U_{0,2}-\frac{1}{3}U_{0,1}\right)-\frac{1}{15}\left(\frac{4}{3}U_{0,1}-\frac{1}{3}U_{0,0}\right)$
$U_{2,0}=U_{0,0}\left(\frac{1}{15\times 3}\right)-U_{0,1}\left(\frac{16}{15\times 3}+\frac{4}{15\times 3}\right)+U_{0,2}\left(\frac{16\times 4}{15\times 3}\right)$
$U_{2,0}=U_{0,0}\left(\frac{1}{45}\right)-U_{0,1}\left(\frac{4}{9}\right)+U_{0,2}\left(\frac{64}{45}\right)$
The formula gives us :
$U_{2,0}=U_{0,0}\left(\frac{4^0}{(1-4)(1-16)}\right)+U_{0,1}\left(\frac{4^1}{(4-1)(1-4)}\right)+U_{0,2}\left(\frac{4^3}{(16-1)(4-1)}\right)$
$U_{2,0}=U_{0,0}\left(\frac{1}{45}\right)+U_{0,1}\left(\frac{-4}{9}\right)+U_{0,2}\left(\frac{64}{45}\right)$
 [/INST] Let $S$ be the shift operator on sequences. That is, for any sequence, $a$,
$$
(Sa)_i=a_{i+1}\tag{1}
$$
Then, the recursion becomes
$$
U_n=\frac{c^nS-I}{c^n-1}U_{n-1}\tag{2}
$$
Consider the polynomial
$$
\prod_{k=1}^n\left(c^kx-1\right)=\sum_{p=0}^na_{n,p}x^p\tag{3}
$$
We have that $a_{n,0}=(-1)^n$ and since each $x=c^{-k}$, for $1\le k\le n$, is a root of $(3)$, we have
$$
\begin{align}
0
&=\begin{bmatrix}
1&c^{-1}&c^{-2}&\cdots&c^{-n}\\
1&c^{-2}&c^{-4}&\cdots&c^{-2n}\\
1&c^{-3}&c^{-6}&\cdots&c^{-3n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
1&c^{-n}&c^{-2n}&\cdots&c^{-n^2}
\end{bmatrix}
\begin{bmatrix}
a_{n,0}\\
a_{n,1}\\
a_{n,2}\\
\vdots\\
a_{n,n}
\end{bmatrix}\\
&=\begin{bmatrix}
1&1&1&\cdots&1\\
1&c^{-1}&c^{-2}&\cdots&c^{-n}\\
1&c^{-2}&c^{-4}&\cdots&c^{-2n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
1&c^{1-n}&c^{2-2n}&\cdots&c^{n-n^2}
\end{bmatrix}
\begin{bmatrix}
c^{-0}a_{n,0}\\
c^{-1}a_{n,1}\\
c^{-2}a_{n,2}\\
\vdots\\
c^{-n}a_{n,n}
\end{bmatrix}\tag{4}
\end{align}
$$
That is, $c^{-p}a_{n,p}$ is proportional to $(-1)^p$ times the determinant of the submatrix gotten by removing column $p$ from the matrix in $(4)$. Each of those submatrices is a Vandermonde matrix. Thus, we can compute
$$
\begin{align}
c^{-p}a_{n,p}
&=\frac{\displaystyle(-1)^p\prod_{k=1}^n(1-c^{-k})}{\displaystyle\prod_{k=0}^{p-1}(c^{-p}-c^{-k})\prod_{k=p+1}^n(c^{-k}-c^{-p})}\\
&=\frac{\displaystyle c^{p(p-1)/2}\prod_{k=1}^n(c^k-1)}{\displaystyle\prod_{k=1}^p(c^k-1)\prod_{k=1}^{n-p}(1-c^k)}\tag{5}
\end{align}
$$
Thus, using $(3)$ and $(5)$, we get
$$
\prod_{k=1}^n\frac{c^kx-1}{c^k-1}=\sum_{p=0}^n\frac{\displaystyle c^{p(p+1)/2}}{\displaystyle\prod_{k=1}^p(c^k-1)\prod_{k=1}^{n-p}(1-c^k)}x^p\tag{6}
$$
Combining $(2)$ (repeatedly) and $(6)$ yields
$$
\begin{align}
U_n
&=\left[\prod_{k=1}^n\frac{c^kS-I}{c^k-1}\right]U_0\\[6pt]
&=\sum_{p=0}^n\frac{\displaystyle c^{p(p+1)/2}}{\displaystyle\prod_{k=1}^p(c^k-1)\prod_{k=1}^{n-p}(1-c^k)}S^pU_0\tag{7}
\end{align}
$$
Element $0$ of $(7)$ is the equation desired.

Finding A Perpendicular Vector
Suppose we have $n$ linearly independent vectors, $\{v_k\}$, in $\mathbb{R}^{n+1}$ and we want to find a vector perpendicular to all of them. Arrange the $n$ vectors as the bottom rows of an $n{+}1\times n{+}1$ matrix, with an unknown vector, $u$, as the top row:
$$
M=\begin{bmatrix}
u_0&u_1&u_2&\dots&u_n\\
v_{1,0}&v_{1,1}&v_{1,2}&\dots&v_{1,n}\\
v_{2,0}&v_{2,1}&v_{2,2}&\dots&v_{2,n}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
v_{n,0}&v_{n,1}&v_{n,2}&\dots&v_{n,n}\\
\end{bmatrix}\tag{8}
$$
Using Laplace's formula for the determinant, we get
$$
\det(M)=u_0\det(M_0)-u_1\det(M_1)+u_2\det(M_2)-u_3\det(M_3)+\dots\tag{9}
$$
where $M_k$ is the $n\times n$ matrix formed by removing the top row and column $k$ from $M$. If we replace $u$ by any of the $v_k$, $\det(M)=0$. That is, the vector
$$
\begin{bmatrix}\det(M_0),-\det(M_1),\det(M_2),\dots,(-1)^n\det(M_n))\end{bmatrix}\tag{10}
$$
is perpendicular to each of the $v_k$.

A Shortcut With Particular Vandermonde Determinants
Suppose we have the $n\times n{+}1$ Vandermonde matrix
$$
X=\begin{bmatrix}
x_0^0&x_1^0&x_2^0&\dots&x_n^0\\
x_0^1&x_1^1&x_2^1&\dots&x_n^1\\
x_0^2&x_1^2&x_2^2&\dots&x_n^2\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
x_0^{n-1}&x_1^{n-1}&x_2^{n-1}&\dots&x_n^{n-1}\\
\end{bmatrix}\tag{11}
$$
Let $X_p$ be the submatrix of $X$ with column $p$ removed. Then, using the formula for the determinant of a Vandermonde matrix, we have
$$
\det(X_p)=\frac{\displaystyle\prod_{0\le j\lt k\le n}(x_k-x_j)}{\displaystyle\prod_{i=0}^{p-1}(x_p-x_i)\prod_{i=p+1}^n(x_i-x_p)}\tag{12}
$$
that is, the products in the denominator remove the terms in the numerator that contain $x_p$. Since the numerator in $(12)$ does not depend on $p$, we can factor out the numerator, for example, when computing a vector parallel to
$$
\begin{bmatrix}
\det(X_0),-\det(X_1),\det(X_2),\dots,(-1)^n\det(X_n)
\end{bmatrix}\tag{13}
$$
as is done in $(5)$.
</s>