Recursive problem - Staircase

Solution 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}

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

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