$$\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.