Waring's Problem and the floor function - solving a recurrence relation by hand First-time poster here. While doing some research on Waring's problem and the term $\{(3/2)^n\},$ I determined that the following recurrence relation holds for a certain sequence (here $n$ is a fixed, positive integer):
$$r_{k}={n \choose k}+\frac{1}{2}r_{k-1}, r_0=1;\,0\leq k\leq n$$
Mathematica gave me the result $r_k = 3^n/2^k-2 {n\choose k+1} {}_{2}F_1(1,k-n+1;k+2;-2),$ which I was able to use with fruitful results, but I have no idea how to derive it by hand (here ${}_2F_1$ is the hypergeometric function). If someone could show me, I would be grateful. I'd also be willing to post a rough draft of my paper if someone was interested. Thanks!
 A: After a while, I used the method of generating functions to solve this recurrence. Let $R(x) = \sum_{k=0}^{\infty}r_k x^k$ and let the $r_k$ be given by
$$r_{k}={n \choose k}+\frac{1}{2}r_{k-1}, r_0=1;\,0\leq k\leq n$$
Then:
$$R(x) = \sum_{k=0}^{\infty} r_k x^k = 1+\sum_{k=1}^{\infty}r_k x^k = 1+\sum_{k=1}^{\infty}\left ( {n \choose k} + \frac{1}{2} r_{k-1}\right ) x^k$$
$$= 1+ \sum_{k=1}^{\infty} {n \choose k} x^k+\sum_{k=1}^{\infty}\frac{1}{2} r_{k-1} x^k$$
$$= \sum_{k=0}^{\infty} {n \choose k} x^k+\frac{x}{2}\sum_{k=0}^{\infty} r_{k} x^k$$
$$= \sum_{k=0}^{\infty} {n \choose k} x^k+\frac{x}{2}R(x)$$
Collecting the $R(x)$ terms on the left, we have:
$$\left(1-\frac{x}{2}\right) R(x) = \sum_{k=0}^{\infty} {n \choose k} x^k$$
$$ R(x)=\left(1-\frac{x}{2}\right)^{-1} \cdot \sum_{k=0}^{\infty} {n \choose k} x^k $$
$$R(x)=\sum_{k=0}^{\infty}2^{-k}x^k \cdot \sum_{k=0}^{\infty} {n \choose k} x^k  = \sum_{k=0}^{\infty} \left ( \sum_{i=0}^k 2^{-(k-i)} {n \choose i} \right ) x^k,$$
which immediately gives:
$$r_k =2^{-k} \sum_{i=0}^k 2^{i} {n \choose i}$$
Manipulating the indices of summation, we have:
$$ r_k = 2^{-k} \sum_{i=0}^k 2^i {n \choose i} = 2^{-k} \sum_{i=0}^n 2^i {n \choose i} - 2^{-k} \sum_{i=k+1}^n 2^i {n \choose i}$$
$$r_k = 3^n2^{-k} -  2^{-k} \sum_{i=k+1}^n 2^i {n \choose i} = 3^n2^{-k} - 2^{-k}\sum_{i=0}^{n-k-1} 2^{i+k+1} {n \choose i+k+1}$$
$$
r_k = 3^n2^{-k} - 2 \sum_{i=0}^{n-k-1} 2^{i} {n \choose i+k+1} = 3^n2^{-k} - 2 \sum_{i=0}^{\infty} 2^{i} {n \choose i+k+1}
$$Writing out the Pochhammer symbols, we have
$$
\binom{n}{ i + 1 + k}=\binom{n}{k+1}\frac{ (n-k-i)_i}{(k+2)_i}
$$Then the last sum is exactly ${}_2F_1(1,n-k-i;k+2;2)$, which is the same as what Mathematica gave (using the negative relation of the Pochhammer coefficients for the second term).
