# Find Maximum of any discrete function (not necessarily a PDF)

How can we find the maximum of any discrete function, say

$$f(n)=\frac{(n+1)^2}{2^n},\quad n\in \mathbb{N}$$

that is not the PDF of any distribution? (This query is unrelated to statistics.)

By generating observations, we can obtain the maximum to be $$9/4$$ when $$n=2$$. However, other less rigourous methods using inequalities give poor estimates for this maximum point.

Wrong Approach 1 (Binomial Expansion):

$$2^n = (1+1)^n\ge \begin{pmatrix}n\\2\end{pmatrix}\implies \frac{(1+n)^2}{(1+1)^n}\le \frac{2(1+n)^2}{n(n-1)}=\frac{2\left(1+\frac{1}{n} \right)^2}{1-\frac{1}{n}}\le 2 \quad(n\to \infty )$$

Wrong Approach 2 (Bernoulli Inequality):

$$2^n=(1+1)^n\ge 1+n(1)\implies \frac{(1+n)^2}{(1+1)^n}\le\frac{(1+n)^2}{1+n}=1+n\to \infty \quad (n\to \infty )$$

How can we find the exact maximum point? If we try to differentiate with respect to $$n$$, we can get $$n\approx 1.88$$, then we can try $$n=1$$ and $$n=2$$, but differentiation is just the wrong approach for a discrete function.

• Why do you say that differentiation is the wrong approach? That is the best approach for this question. – Kavi Rama Murthy Apr 20 at 5:06
• Extend this function to positive real numbers, then use derivatives to show that it grows up to some point and then decreases (i.e. it is unimodal). The discrete maximum occurs at one of the immediate integer neighbors of the continuous maximum point, because it is less than those values on either side, by monotonicity. This works for any unimodal function. – Conifold Apr 20 at 5:26
• @Conifold : I think it is generally not advisable to differentiate discrete distributions because many complications can occur - the least of which we need to check for differentiability. For instance, consider $f(n) = |n^2 - 2|$, where $n$ is any natural number. It has minimum value at $n=1$, but it is not differentiable at $x=\sqrt{2}$. The function itself is not easy to differentiate. – NetUser5y62 Apr 20 at 5:53
• The question is whether the discrete function extends to a (piecewise) differentiable function. If so, the use of calculus is highly effective, and hence advisable. The points of non-differentiability should be treated as additional critical points and tested for potential maxima/minima along with zeros of the derivative on each interval between them. In your example you have three such intervals separated by $\pm\sqrt{2}$. Note that you will have to do the same when investigating maxima/minima of the continuous function $f(x) = |x^2 - 2|$, it is not the discreteness that makes the difference. – Conifold Apr 20 at 6:26

## 2 Answers

Hint: Consider the ratio of successive terms $$\dfrac{f(n)}{f(n-1)}$$, for $$n\ge 1$$. (This ratio here equals $$\dfrac{(n+1)^2}{2n^2}$$.) Try and find for which values of $$n$$ we have $$\color{blue}{\dfrac{f(n)}{f(n-1)} \ge 1}$$. Can you see how to use this information to find which $$n$$ maximises $$f(n)$$?

Hint: Prove that $$\frac{(n+1)^2}{2^n}\le \frac{9}{4}$$ The equal sign holds if $$n=2$$ This is equivalent to $$(n+1)^2\le 9\cdot 2^{n-2}$$. You can prove this by induction.

• I am afraid this is precisely the result I am unable to prove. Moreover, we are guessing the upper bound and then trying to prove it. We cannot guess the bound for more complicated expressions – NetUser5y62 Apr 20 at 6:12