Question

Question regarding a summation equality: \[\sum_{k=0}^n n(n-1)\dotsb(n-k+1) \leq \sum_{k=0}^n n^k \]

Answer 1

I don't necessarily need a rigorous proof (although I wouldn't mind that), but how can I show myself that the above equality is true for all $n$?

Well, I'm seeing it now. on the left and right side of the equation we will have on average
n+k2
terms for each addend. On the right instead of counting down from n to n-k+1, each of those terms is equal to n. On the left each term is less than or equal to n... Makes sense now.

Answer 2

\[\sum_{k=0}^{n}n^2-kn+n \le \sum_{k=0}^{n}n^k\]

take log of both sides

\[\sum_{k=0}^{n}2\ln n-\ln(kn)+\ln n \le \sum_{k=0}^{n}k \ln n\]

factor out ln n

\[\sum_{k=0}^{n}\ln n \left( 2-1+\ln k+1 \right)\le \sum_{k=0}^{n}k \ln n\]

Divide by ln n

\[\sum_{k=0}^{n} 2+\ln k \le \sum_{k=0}^{n}k\]

Get rid of the summation notation

\[2+\ln k \le k\]

and just solve the inequality

Answer 3

That is very good, but how do I show that \[ \sum_{k=0}^n n(n-1)\dotsb(n-k+1) \leq \sum_{k=0}^{n}n^2-kn+n \]


Also, I think the step after "factor out ln n" should be:

\[\sum_{k=0}^{n}\ln n \left( 2-1-\ln k+1 \right)\le \sum_{k=0}^{n}k \ln n\]
which would give \[2-\ln k \le k\] so by that logic, the summation is true for integer values of n > 1, although I don't quite follow the very first step.