6
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ Why do you say that differentiation is the wrong approach? That is the best approach for this question. $\endgroup$ Commented Apr 20, 2019 at 5:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – Conifold
    Commented Apr 20, 2019 at 5:26
  • $\begingroup$ @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. $\endgroup$ Commented Apr 20, 2019 at 5:53
  • 4
    $\begingroup$ 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. $\endgroup$
    – Conifold
    Commented Apr 20, 2019 at 6:26

2 Answers 2

6
$\begingroup$

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)$?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Apr 20, 2019 at 6:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .