True story: I was teaching my 11-year old about recursion and this came up... The integer squares, f(n) = n^2 can be generated recursively:
f(1) = 1, f(n) = f(n-1) + 2 n - 1.
So, how does one similarly generate the integer cubes through addition of terms in n?

Bonus 1: How about f(n) via recursion only using previous terms, without using n alone?

Bonus 2: What about for higher powers? Does n^4 have a solution made by adding an integer coefficient cubic in n? How else?

Bonus 3: Is there a general solution to make n^j, for all j using recursion?