Why is solving non-linear recurrence relations "hopeless"? I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like "it's hopeless to solve non-linear recurrence relations in general." Is there a rigorous reason or an illustrative example as to why this is the case? It would seem to me that the correct response would be "we just don't know how to solve them," or "there is no solution using elementary functions," but there might be a solution in the form of, say, an infinite product or a power series or something.
Just for completion, the recurrence relation I'm looking at is (slightly more than just non-linear, and this is a simplified version):
$p_n = a_n b_n\\ a_n = a_{n-1} + c \\ b_n = b_{n-1} + d$
And $a_0 > 0, b_0 > 0, c,d$ fixed constants 

But polynomial recurrence can be mapped to linear recurrences. For example for
$a_{n+1} = a_n^2 + c$ let $b_{m,n} =a_n^m$. Then by the binomial formula:
$$b_{m,n} = (a_{n-1}^2+c)^m = \sum_{j = 0}^mc^{m-j}{m \choose j}a_{n-1}^{2j} = 
\sum_{j = 0}^mc^{m-j}{m\choose j}b_{2j,n-1}$$
and even though it's a two variable linear recurrence you can use a lot of the same types of strategies to solve it as if it was one variable (indeed for any number of variables you can use the same approaches as if it were one variable).
So what's the big deal?
