Can a sequence of elementary operations/algorithm give a specific closed form for a recurrence relation?

Question

$$\color{blue}{\textbf{Tldr : How to prove the following algorithmically without induction?}}$$

$$\color{red} {a_{n} = 1 + \left(\dfrac{n+1}{2n}\right) a_{n-1} \implies a_{n} = \sum _{r=0}^{n} \dfrac{1}{\binom{n}{r}}} $$

Consider the sequence

$$ a_{n} = \sum _{r=0}^{n} \dfrac{1}{\binom{n}{r}} \tag{*}$$

I proved here that it satisfies the recurrence relation $$a_{n} = 1 + \left(\dfrac{n+1}{2n}\right) a_{n-1} \tag{$\dagger$}$$

Now, we can solve this recurrence relation by forming telescopic sums by a sequence of elementary operations (addition, multiplication, compositions of elementary functions etc.), to obtain an alternate closed form.

In particular,

$$\dfrac{2^n}{n+1}a_n - a_1 = \sum_{r=2}^{n} \left(\dfrac{2^r}{r+1} a_{r} - \dfrac{2^{r-1}}{r} a_{r-1} \right) = \sum_{r=2}^{n} \dfrac{2^r}{r+1}$$

Which, after simplifying, gives the elegant identity,

$$ a_n = \sum_{r=0}^{n} \dfrac{1}{\binom{n}{r}} = \left(\dfrac{n+1}{2^{n+1}}\right) \sum_{r=1}^{n+1} \dfrac{2^r}{r} $$

Question : Is it possible to recover the original closed form $(*)$, without prior knowledge of it and just from the recurrence $(\dagger)$ and some initial values, by using a sequence of elementary operations (similar to what was done for the other closed form obtained here)?

Elaborating on what I'm looking for :

• I'm looking for an algorithm to get $(*)$ from $(\dagger)$, involving finite combinatorial methods (elementary operations, binomial transforms etc.), so Integrals are excluded.

• I wrote "without prior knowledge" to avoid the use of ansatz. Methods based on induction assume prior knowledge and are excluded.

I'm seeking an algorithm so that it can be generalized to a large class of recurrence relations.

Answer 1

This is not an answer, but is too long for a comment. Below is a natural, ansatz-free method that surprisingly leads to the double of the wished result. I suspect that with a little more ingenuity, it can lead to a full solution.

So, we start with the recurrence relation

$$ a_n=1 + \left(\dfrac{n+1}{2n}\right) a_{n-1} \tag{$A_0$} $$

Step 1 : we are optimistic, and assume that $(a_n)$ has a limit, in other words that there has an expansion of the form $a_n=l+o(1)$. Passing to the limit in $(A_0)$ above, we see that $l=2$. This suggests the rescaling $a_n=2+b_n$, which yields

$$ b_n=\dfrac{1}{n} + \left(\dfrac{n+1}{2n}\right) b_{n-1} \tag{$B_0$} $$

Step 2 : we are optimistic, and assume that $(a_n)$ has a Taylor expansion of the form $a_n=2+\dfrac{l}{n}+o(\dfrac{1}{n})$. Then $l$ is the limit of the sequence $a_n^1=nb_n$, so let us see what recurrence relation is satisfied by this new sequence. It turns out to be

$$ a^1_n=1 + \left(\dfrac{n+1}{2(n-1)}\right)a^1_{n-1} \tag{$A_1$} $$

Step $3$: Passing to the limit in $(A_1)$ above, we see that the limit of $a^1_n$ is $2$ if it exists. This suggests the rescaling $a^1_n=2+b^1_n$, which yields

$$ b^1_n=\dfrac{2}{n-1} + \left(\dfrac{n+1}{2(n-1)}\right) b^1_{n-1} \tag{$B_1$} $$

Step 4: arguing as in step 2, let us now put $a_n^2=(n-1)b^1_n$ (we use $n-1$ rather than $n$, because of the $n-1$ in the denominator of $(B_1)$ above). We deduce

$$ a^2_n=2 + \left(\dfrac{n+1}{2(n-2)}\right)a^1_{n-1} \tag{$A_2$} $$

Iterating this argument, we obtain for every $k\geq 0$,

$$ \begin{array}{lclc} a^k_n &=& k! + \left(\dfrac{n+1}{2(n-k)}\right)a^k_{n-1} & (A_k) \\ b^k_n &=& \dfrac{(k+1)!}{2(n-k)} + \left(\dfrac{n+1}{2(n-k)}\right)b^k_{n-1} & (B_k) \end{array} $$

and we have the successive identities

$$ \begin{array}{lcl} a_n &=& 2+ \dfrac{1}{n}a^1_n \\ &=& 2+ \dfrac{2}{n} +\dfrac{1}{n(n-1)}a^2_n \\ &=& 2+ \dfrac{2}{n} +\dfrac{4}{n(n-1)} +\dfrac{1}{n(n-1)(n-2)}a^3_n \\ &=& \ldots \\ \end{array} $$

At the $r$-th step ($0\leq r \lt n $) of this iteration, we obtain

$$ a_n = \sum_{k=0}^{r}\dfrac{2k!}{n(n-1)\ldots(n-(k-1))} + \dfrac{1}{n(n-1)(n-2)\ldots(n-r)}a^r_n $$

In other words,

$$ a_n = \sum_{k=0}^{r}\dfrac{2}{\binom{n}{k}} + \dfrac{(r+1)!}{\binom{n}{r+1}}a^r_n \tag{1} $$

In particular, when $r=n-1$,

$$ a_n = \sum_{k=0}^{n-1}\dfrac{2}{\binom{n}{k}} + n!a^{n-1} _n \tag{2} $$