Upper bound for $\sum_{j=0}^k \alpha^j(\beta j)^{k-j}$

Question

I am looking for an upper bound for the sum $$\sum_{j=1}^n \alpha^j(\beta j)^{n-j}$$ for constants $\alpha,\beta <1$ and some $n\in\mathbb{N}$ which is "better" than simply replacing $j$ by $n$. I tried using the integral $1+\int_{1}^n \alpha^x(\beta x)^{n-x} dx$ but then again I get stuck integrating these terms. So I tried to estimate $x^{n-x}$ by its maximum in the intervall $[1,k]$ but I get stuck when trying to solve the equation for the first derivative $-x^{n-x - 1} (x + x\log(x) - y)=0$. Do you have any suggestions?

Answer 1

I assume in what follows $\beta>\alpha$. In the opposite case the order in the differences using $\alpha$ and $\beta$ within the $\log(\tau_{\alpha\beta})$ have to be switched.

Applying the reasoning as here, and using the notation $H_{\alpha}^{\beta}(n)$ for the some as well as $a,b$ as in the other post but additionally with $a+b<1$, I obtain for the lower bound the following result. First, I define $$\log(\tau_{\alpha\beta})=\log(\alpha^{an}\beta^{bn+1}-\alpha^{bn+1}\beta^{an})-\log(\beta-\alpha)+(n-(a+b)n)\log(\beta)$$ such that $$\log(H_{\alpha}^{\beta}(n))\geq (1-b)n\log(n)+(1-b)n\log(a)+\log(\tau_{\alpha\beta})$$ and, therefore, $$\liminf_{n\to\infty}\dfrac{\log(H_{\alpha}^{\beta}(n))}{n\log(n)}\geq 1-b.$$

For the upper bound I use that $H_{\alpha}^{\beta}(n)\leq H(n)$ such that the argument from the other post using $H(n)\leq n!$ still works for the upper bound. Therefore, we obtain also $$\limsup_{n\to\infty}\dfrac{\log(H_{\alpha}^{\beta}(n))}{n\log(n)}\leq 1$$ such that $H_{\alpha}^{\beta}(n)$ is $\Theta(n\log(n))$. Iguess it becomes more interesting if $\alpha$ and $\beta$ depend inversely on $n$ since then they might enforce a slower growth behavior.