I have a non-linear recurrence relation I derived from observing the first few terms, and wish to prove by induction it is true for all $n \in \mathbb{Z}^+$.
$$P_n = P_{n-1}(P_{n-1} + 1)$$
For reference, $P_n$ denotes the total number of paths from a source vertex to a destination vertex in a directed graph (Hanoi graph). The source vertex in this case is the very top named 111, and destination the bottom right 333.
I understand it is difficult to solve non linear recurrences, does anyone know of a way I can prove this formula, either through solving or otherwise?