I was basically given a Pascal Triangle formula and asked to provide an asymptotic upper bound.
I have done some work and ended with expression below
${n^k} \ge {n(n-1)^{(k-1)}}$
now I am trying to justify that LHS $\ge$ RHS is always true for all positive integer n and k
tried to use proof by induction but stuck with the second phase, can you even prove with inequality, I might be using the wrong prove, direct me with anything useful thanks
You don't need induction to prove this. For any positive integer $k$ and $n(>1)$,
$n^k=n.n^{k-1}$
So, the question just reduces to show that
$n^{k-1}\geqq (n-1)^{k-1}$
which is true since $\frac{n}{n-1}\geqq1$ for all $n>1$.
It holds trivially if $n=1$