Turn recursive definition of a function into its close form

Question

I'm creating a tree diagram, and I'm trying to calculate the amount of white spaces I need at the left side. As you can already see this is done in a program.

The formula goes like this:

$$ \text{Let }w=\text{width of bottom row},r=\text{row}\\ Padding(w,r)=\left\{ \begin{array}{lr} w & : r=0\\ Padding(w/2-1,r-1) & : r > 0 \end{array} \right. $$

Pseudocode if you prefer them:

width := (Math.pow(2, row)*2-1)*2, output := "",
padding := width;
for(j = 0; j < row; j++){
    padding = padding /2 - 1;
}

I don't like loops and I want to see if there's a similar formula that takes $\text{row}$ as the variable and directly gives the amount of spaces (padding) of the left.

Answer 1

One can prove by induction that $p(w,r) = \frac{w}{2^r} - 2+\frac1{2^{r-1}}$ for $r\geq 1$.

Indeed, $p(w,1) = \frac{w}{2}-1 = \frac{w}{2^1} - 2 + \frac1{2^0}$.

For $r>1$, we have $$\begin{align*} p(w,r) &= p(\frac{w}{2} - 1, r-1)\\ &= \frac{\frac{w}{2}-1}{2^{r-1}} -2 + \frac{1}{2^{r-2}} & \text{by induction hypothesis} \\ &= \frac{w}{2^r} - \frac{1}{2^{r-1}} - 2 + \frac1{2^{r-2}}\\ &= \frac{w}{2^r} - 2 + \frac1{2^{r-1}}. \end{align*} $$