Prove $\text{L}(n,k)\le{n\brace k}$ without induction

Question

Define $$ \text{L}(n,k):=\frac{1}{2}\left(k^{2}+k+2\right)k^{\left(n-k-1\right)}-1$$ Then :$$\text{L}(n,k)\le{n\brace k}$$

Where $1 \le k \le n-1$ and $n \in \mathbb N_{\ge2}$ and ${n\brace k}$ denotes Stirling numbers of the second kind.

The inductive proof of this relation is available here.

I already know how to prove this using induction, but where does exactly this lower bound comes from? In my opinion there should be a way to prove this without using induction.

Answer 1

This was intended to be a comment, but got too big:

Notice that if $k=n-1,$ $L(n,k)=\binom{n}{2},$ also if $k=1,$ $L(n,k)=1$ and if $k=2,$ $L(n,k)=2^{n-1}-1.$ All of these cases agree with Stirling numbers of the second kind. Consider $n-1>k>2,$ and take $n>5$

Notice that $L(n,k)$ can be written as $$L(n,k)=\left (\binom{k}{2}+\binom{k}{1}+\binom{k}{0}\right )\cdot k^{n-k-1}-1<\left (\color{red}{\binom{k}{2}}+\color{blue}{\binom{k}{1}}+\binom{k}{1}\right )\cdot k^{n-k-1}\color{orange}{-1}.$$ Consider the following escenarios:

1. We place number $1,2,\cdots ,k$ in different blocks and then we have $k^{n-k}$ ways to place the other numbers in this blocks. We color the expression in $\color{blue}{blue.}$
2. We choose $2$ numbers from $1,2,\cdots ,k$ that will share block and we put $n$ in a block of its own, so we have $k$ blocks and there are $\binom{k}{2}k^{n-k-1}$ ways to place the remaining $n-k-1$. We color the expression in $\color{red}{red}$
3. We put $n,n-1,\cdots n-k+1$ in different blocks and the rest have $k^{n-k}$ ways to be placed. I believe the $\color{orange}{-1}$ will take care of the case $k=n/2$ in which we can pair $i$ with $n-i+1$ and we will have the same partition twice(from case 1.). We color in black this expression.

I think one can show that these three escenarios are disjoint(except for the $\color{orange}{case}$ i mention in the 3rd case)