Find a closed formula of the amount of balls of a three side pyramids that is constituted of only balls.
A three sided pyramid contains $1$ ball on the first layer, $3$ on the second one, $6$ on the $3^{rd}$ layer, 10 on the $4^{th}$ layer, 15 on the $5^{th}$ one and 21 on the $6^{th}$.
So for the amount of balls just add the previous numbers up to get the following sequence.
$$1,4,10,20,35,54,\ldots $$
If you perform the finite difference method of Newton you'll get. $$3,6,10,15,21,\ldots $$ $$3,4,5,6,\ldots $$ $$1,1,1,$$
So the closed formula needs to have a polynomial of $4^{th}$ degree. $P(x) = ax^4 + bx^3 + cx^2 + dx + e $
I've already solved the matrix of these unknowns. But if you want to do it on your own feel free to verify my solution.
I got that $P(x) = \frac 16 x^3 + \frac 12 x^2 + \frac 13 x$
Now I need to prove this with induction.
$\underline {n=1}$: $\frac 16 + \frac 12 + \frac 13 = 1 $
$\underline {n=k}$: Suppose this formula holds for $P(k) = \frac 16 k^3 + \frac 12 k^2 + \frac 13 k$ with $k\gt 0$
$\underline {n=k+1}$:
$P(k+1) = P(k) + \ldots$
From here on I'm left blank on what to do next because I don't know what to add with $P(k)$ to get $P(k+1)$.
Although you solved the recurrence relation, you didn't actually find what it was. However, just note that $$P(k+1)=P(k)+(P(k+1)-P(k))$$