Solve recurence relation $T(n) = 5T(n-1) + n^{\sqrt n}$ I need to solve the recurence relation:
$$T(n) = 5T(n-1) + n^{\sqrt n}$$
I am trying to solve it, but it can't be done by any methods I know (Master theorem and etc.)$
Any tips?
 A: As Sil said, your "closed-form" expression is
$$T(n)=5^n \left( T(0) + \sum_{k=1}^n 5^{-k} k^{\sqrt{k}} \right) = 5^n \left( T(0) + \sum_{k=1}^\infty 5^{-k} k^{\sqrt{k}} - \sum_{k=n+1}^\infty 5^{-k} k^{\sqrt{k}} \right) \, .$$
You can then estimate $$\sum_{k=n+1}^\infty 5^{-k} k^{\sqrt{k}} \leq \int_{n}^\infty 5^{-k} k^{\sqrt{k}} \, {\rm d}k = \int_{n}^\infty e^{\sqrt{k}\log(k) - k \log(5)} \, {\rm d}k = \int_{n}^\infty e^{-k\log(5) \left(1-\frac{\log(k)}{\sqrt{k}\log(5)}\right)} \, {\rm d}k \, ,$$
and you will find that $$1-\frac{\log(k)}{\sqrt{k}\log(5)}$$
has a unique minimum at $k=e^2$ and so
$$\sum_{k=n+1}^\infty 5^{-k} k^{\sqrt{k}} \leq \int_n^\infty e^{-k\left(\log(5)-2/e\right)} \, {\rm d}k = O\left(e^{-n\left(\log(5)-2/e\right)}\right) \, .$$
I doubt you will find closed form for your constant $$\sum_{k=1}^\infty 5^{-k} k^{\sqrt{k}} = 0.406435769... \, .$$
A: Since the recurrence relation is linear, we can write $T(n)=T_h(n)+T_p(n)$.
The homogenous solution is given by $T_h(n)=T(0)5^{n-1}$. Writing $n^{\sqrt{n}}=5^{\frac{\log(n)}{\log(5)}\sqrt n}$ it is clear that $T_h(n)\gg n^{\sqrt n}$ for $n\gg1$ since $n \gg \sqrt{n}\log(n)$ in this regime. It follows that to leading order $T(n)=T_h(n)+o(5^{n-1})$. This is the principle of dominated balance.
