# Find the index of the largest element in a sequence $x_n = (\alpha + \beta)^{-n} \sum_{k=0}^nc^{n-k}\beta^kx_{n-k}x_k$.

As in the title i want to find the largest element of the given sequence. Excuse me for the vague title, MSE limits the title to 150 symbols.

To give you some context here is the full problem statement:

Let $x_0 = 1$ and $x_1 = c$ $$x_n = (\alpha + \beta)^{-n} \sum_{k=0}^nc^{n-k}\beta^kx_{n-k}x_k$$ Where $n \in \mathbb N$ and $n \ge 2$ and $\alpha, \beta, c > 0$. Find the general term formula and index of the largest element of the given sequence.

I've found the general term formula by expanding several first terms of the given sequence and observing a pattern. The solutions is very large so i'm not going to post it here. Finally I got that:

$$x_2 = {c^2 \over 2} \\ x_3 = {c^3 \over 2\cdot 3} \\ x_4 = {c^4 \over 2\cdot 3 \cdot 4} \\$$

So based on the above the general term is in the form:

$$x_n = { c^n \over n!}$$

Second part of the problem statement asks to find the index of the largest element. After a failed attempt to find it analytically I made a graph of the general term but it's not very clear from it what that number $n_{max}$ is.

How could I find the index of the largest element without involving the graph?

Update based on the answers below

Using @Andrei's suggestion i've come across the following inequalities. Let $k = n_{max}$:

$$\cases{ {c \over k} > 1 \\ \frac{1+k}{c} > 1 }$$

After subtructing those equations:

$${c \over k} - {{1+k} \over c} > 0 \iff \\ \iff \frac{c^2 - k - k^2}{ck} > 0$$

Both $k$ and $c$ are known to be greater than $0$, so:

$$c^2-k-k^2 > 0$$

One of the root of this equation appears to be very close to the maxima of $c^n \over n!$

That root is:

$$k = \frac{{1- \sqrt{1+4c^2}}}{-2}$$

Here is a link to visualisation in Desmos

• And $k = \frac{{1- \sqrt{1+4c^2}}}{-2}=c-\frac{1}{2}+\frac{1}{8 c}+O\left(\frac{1}{c^3}\right)$ !! – Claude Leibovici Aug 10 '18 at 10:01
• @ClaudeLeibovici indeed, looking through your answer once again i conclude that $max\{x_n\} = x_{\lceil n \rceil}$ for $c \ge 2$ – roman Aug 10 '18 at 10:12
• $c$ seems to be a very good candidate ! Cheers. – Claude Leibovici Aug 10 '18 at 10:28

In the real domain, consider the function $$f(n)=\frac {c^n}{n!}$$ The first derivative $$f'(n)=\frac{c^n \left(\log (c)-H_n+\gamma \right)}{\Gamma (n+1)}$$ cancels when $H_n=\log(c)+\gamma$ and this is the equation to solve.

Let us suppose that $n$ is large and using the asymtotics of the harmonic numbers, we then have $$\log (c)-H_n+\gamma=\log (c)+\log \left(\frac{1}{n}\right)-\frac{1}{2 n}+O\left(\frac{1}{n^2}\right)$$ The zero of this truncated series is given in terms of Lambert function $$n_*=-\frac{1}{2\, W\left(-\frac{1}{2 c}\right)}$$ So $\lceil n_* \rceil \pm 1$ is probably the answer to consider.

Let me try with $c=6.789$; this would give $n_*=6.26852$ and $\lceil n_* \rceil=7$. Computing the $f(n)$ $$\left( \begin{array}{cc} n & f(n) \\ 1 & 6.789 \\ 2 & 23.0453 \\ 3 & 52.1514 \\ 4 & 88.514 \\ 5 & 120.184 \\ 6 & 135.989 \\ 7 & 131.889 \\ 8 & 111.925 \\ 9 & 84.4285 \\ 10 & 57.3185 \end{array} \right)$$

What you could also notice is that, if $c$ is large, by Taylor, we should have $$n_*=c-\frac{1}{2}-\frac{1}{8 c}+O\left(\frac{1}{c^2}\right)$$

Hint: If you are looking for the largest element, the elements right before and right after have to be smaller. From the formula you have for $x_n$, I would write the ratios $$R_\pm=\frac{x_{n_{max}}}{x_{n_{max}\pm 1}}$$ Both these ratios are greater than $1$.

We have $$\frac{x_n}{x_{n-1}}=\frac{c}{n}$$ If $c>n$, the sequence is increasing, while if $c<n$ the series is decreasing. Note that $c/n$ is always decreasing with increasing $n$, and the limit for large $n$ is $0$. So you have $n_{max}=\lfloor c\rfloor$.

• Your approach is very promising, yet i'm still one step away from the solution – roman Aug 10 '18 at 9:54
• You are complicating it too much. I'll amend my reply – Andrei Aug 10 '18 at 14:16