Recursive problem - Staircase

Question

I

I am working on recursive formulas and I managed to solve the fib formula and got it to

F(0) = 0
F(1) = 1
F(N) = F(N - 1) + F(N - 2)

Now I stumbled on another problem as you can see in the image that's depicting the problem. I need to find a formula but I find it challenging since it's recursive.

I came up with some thoughts:

Let's call the figure P

This is the series I came up with:

   P:                                      1          2        3         4        5
   Number of blocks:                       0          1        7         22       50
   The amount of blocks in the base:       0          1        6         15       22

You can probably see a pattern here. P is determined by adding together the amounts of blocks in each base in the previous figure.

For instance figure 4, has 22 stone blocks in total. We can do that by adding up 15 + 6 + 1 + 0 = 22

You can also see that the width increases by 1 and the length increases by 2 for each P.

The problem I have here is implementing this pattern as a function, just like I did with the Fib series. I appreciate some help.

This is how I've started:

F(1) = 0
F(2) = 1

Answer 1

 P:                              1     2      3      4       5
 number of blocks in the base:   0     1      6      15      22
 total number of blocks, F(P):   0     1      7      22      50

This is how I've started:
  $F(1) = 0$
  $F(2) = 1$

We want a recurrence relation that relates $F(P+1)$ and $F(P),$ were $P$ is the term number according to your table above.

You can also see that the width increases by 1 and the length increases by 2 for each P.

This is the key observation. Thus, \begin{align}F(P+1)&=F(P)+\text{width $\times$ length of the added rectangle}\\&=F(P)+P\times\text{the $P$th term of the arithmetic sequence with first term $1$ and common difference $2$}\\&=F(P)+P \times \big(1+ (P-1)2\big)\\&=F(P)+2P^2-P.\end{align}

---

Supplement to the above answer

Recap: the above recurrence system is $$F(1)=0,\\F(P+1)=F(P)+2P^2-P\quad (P\in\mathbb N).$$

• It describes a sequence with a constant “jerk” (third common difference)—in this case, $4$—so it has a cubic closed-form expression.

  So, to derive it, plug $P=1,2,3$ into $$F(P)=aP^3+bP^2+cP+d$$ and solve simultaneously:$$\left. \begin{array}{l} 0&=&a+b+c+d\\ 1&=&8a+4b+2c+d\\ 7&=&27a+9b+3c+d\\ 22&=&64a+16b+4c+d \end{array} \right\} \iff a = \frac23 , b = -\frac32 , c = \frac56 , d = 0.$$ Thus, $$F(P)=\frac23P^3-\frac32P^2+\frac56P.$$

• Alternatively, its closed form can be derived using telescoping cancellation: \begin{align}F(P+1)-F(P)&=2P^2-P\\&\vdots\\&\vdots \\F(P+1)-F(1)&=2(1^2+2^2+\ldots+P^2)-(1+2+\ldots+P)\\F(P+1)-0&=2\left(\frac{P(P+1)(2P+1)}6\right)-\left(\frac{P(P+1)}2\right)\\F(P)&=2\left(\frac{(P-1)P(2(P-1)+1)}6\right)-\left(\frac{(P-1)P}2\right)\\&=\frac23P^3-\frac32P^2+\frac56P.\end{align}

Answer 2

Well, in this case you aren't just adding the two previous terms. You're adding a layer around the blocks.

Notice that in the Nth layer, you are adding $(N-1) * (2N-3)$ blocks.

So, a plausible function would be $f(N) = f(N-1) + (N-1)(2N-3)$, where $f(1)=0, f(2)=1$.

Answer 3

Here's an approach very much in the spirit of recursion: Let $f(n)$ denote the number of blocks in the $n$-th pile, and $w(n)$ and $l(n)$ the width and length of $n$-th layer. Here the first pile consists of one block, so that $f(0)=w(0)=l(0)=0$ and $f(1)=w(1)=l(1)=1$. Then we get the recursive formula $$f(n+1)=f(n)+w(n+1)\cdot l(n+1)\tag{1}.$$ As you note, going from one layer to the next, the width increases by $1$ and the length increases by $2$, so $$w(n+1)=w(n)+1\qquad\text{ and }\qquad l(n+1)=l(n)+2.$$ These are two simple linear recursions, with solutions $w(n)=n$ and $l(n)=2n-1$. Plugging this back into $(1)$ yields $$f(n+1)=f(n)+n\times(2n-1).$$ It also gives you the direct formula $$f(n)=\sum_{k=1}^nk\times(2k-1).$$ From here you can express $f$ as a polynomial in $n$ using the well-known closed forms for $\sum_{k=1}^nk$ and $\sum_{k=1}^nk^2$.

---

Note that counting the pile of one layer, with one block, as the first pile gives a nicer indexing of the sequence. You get $f(0)=0$ and $f(1)=1$.