Good asymptotic for this recursion?

76 Views Asked by At

Consider some initial integer values and let the integer sequence continue like

$$\begin{align}f(n) &= f(n-1) \\ &+ n(n+1)(n+2)\dots(n+5) f(n-2) \\ &- \frac{ n(n+1)(n+2)\dots(n+5)}{2} f(n-3) \\ &- \frac{ n(n+1)(n+2)\dots(n+5)}{3} f(n-4) \\ &- \frac{ n(n+1)(n+2)\dots (n+5)}{6} f(n-5) \\ &+ K. \end{align}$$

For some positive integer $K$.

Consider the cases where eventually the sequence remains strictly increasing.

What are possible closed forms if any ?

What are the best asymptotics !?

I assume the best(?) asymptotics are something like

$ A ( n ! )^6 $ or $ A ( n!)^5 $ ? ( $ A $ some constant ) Big those estimates seem poor and even kinda ignore the variable $K$.

So i doubt my own guesses.

Not sure how to handle it.

Reminder me of the factorial of hypergeo.

Clearly this is just part of a bigger question ; the similar recursion equations

$$ \sum_i p_i(n) f(n-i) = 0 $$

And perhaps it is useful to think of the related equations

$$ \sum_i p_i(x) f(x/i) = 0 $$

$$ \sum_i p_i(x) f(x/2^i) = 0 $$

And look at their Taylor series solutions ? Those solutions might be found and understood by systems of equations ...

1

There are 1 best solutions below

2
On BEST ANSWER

Under the assumptions that $f$ is positive and strictly increasing we have: $$ \begin{align}f(n) &= f(n-1) \\ &+ n(n+1)(n+2)\dots(n+5) f(n-2) \\ &- \frac{ n(n+1)(n+2)\dots(n+5)}{2} f(n-3) \\ &- \frac{ n(n+1)(n+2)\dots(n+5)}{3} f(n-4) \\ &- \frac{ n(n+1)(n+2)\dots (n+5)}{6} f(n-5) \\ &+ K. \\&\Leftrightarrow\\ f(n)&=f(n-2) \\ &+ (n+1)(n+2)\dots(n+6) f(n-3) \\ &- \frac{ (n+1)(n+2)\dots(n+6)}{2} f(n-4) \\ &- \frac{ (n+1)(n+2)\dots(n+6)}{3} f(n-5) \\ &- \frac{ (n+1)(n+2)\dots (n+6)}{6} f(n-6) \\ &+ K\\ &+ n(n+1)(n+2)\dots(n+5) f(n-2) \\ &- \frac{ n(n+1)(n+2)\dots(n+5)}{2} f(n-3) \\ &- \frac{ n(n+1)(n+2)\dots(n+5)}{3} f(n-4) \\ &- \frac{ n(n+1)(n+2)\dots (n+5)}{6} f(n-5) \\ &+ K\\ &\le f(n-2) \\ &+ (n+1)(n+2)\dots(n+6) f(n-3) \\ &+ n(n+1)(n+2)\dots(n+5) f(n-2) \\ &+ 2K\\ &= \\ &+ (n+1)(n+2)\dots(n+6) f(n-3) \\ &+ (1+n(n+1)(n+2)\dots(n+5)) f(n-2) \\ &+ 2K \end{align}$$ Further we have then $$ \begin{align} f(n) &\le\\ &+ (n+1)(n+2)\dots(n+6) f(n-3) \\ &+ (1+n(n+1)(n+2)\dots(n+5)) f(n-2) \\ &+ 2K\\ &\le \\ &+ 2(1+n(n+1)(n+2)\dots(n+5)) f(n-2) \\ &+ 2K \end{align} $$ For all $n\ge N$ for some $N$ we further have: $$ f(n)\le c\cdot 2(1+n(n+1)(n+2)\dots(n+5)) f(n-2) $$

You then can solve this recurrence equation, e.g. per WolframAlpha and obtain some bounds using it (you can get an even better than I initially guessed).