This is a consequence of the binomial theorem, which says that
$(x+y)^n=\sum_{k=0}^n\binom{n}kx^ky^{n-k}\;,\tag{1}$
Set $x=m-1$ and $y=1$, and $(1)$ becomes $m^n=\sum_{k=0}^n\binom{n}k(m-1)^k\;,\tag{2}$ without using induction at all.
Applying this twice, you get
$m^n=\sum_{k=0}^n\binom{n}k(m-1)^k=\sum_{k=0}^n\binom{n}k\sum_{i=0}^k\binom{k}i(m-2)^i\;,$
which can also be written $\sum_{k=0}^n\sum_{i=0}^k\binom{n}k\binom{k}i(m-2)^i\;;$
note, though, that this is a bit different from your second formula.
Here is another proof of $(2)$, also not using induction. Imagine that there are $n$ children in a doughnut shop that sells $m$ kinds of doughnut, and each child buys one doughnut. Since each of the $n$ children can choose any of the $m$ types, they can make their choices in $m^n$ different ways.
Now we’ll use a different method to count the number of ways in which they can choose their doughnuts. One of the kinds of doughnut on offer is plain doughnuts. Suppose that $k$ of the $n$ children do not buy plain doughnuts (and of course the other $n-k$ do buy plain doughnuts). Each of these $k$ children buys one of the $m-1$ fancy varieties of doughnut, so they have $(m-1)^k$ ways to make their choices. Thus, for each $k$ from $0$ through $n$ there are $(m-1)^k$ ways for a particular set of $k$ children to choose fancy doughnuts while the other $n-k$ children buy plain doughnuts. There are $\binom{n}k$ different sets of $k$ children, so for each $k$ from $0$ through $n$ there are $\binom{n}k(m-1)^k$ ways to choose the $k$ children who want fancy doughnuts and let them choose their doughnuts. Since any number of the kids can want the fancy doughnuts, the total number of ways that they can pick their doughnuts is $\sum_{k=0}^n\binom{n}k(m-1)^k\;,$ where the $k$-th term of the sum counts the number of ways if exactly $k$ of the kids want fancy doughnuts.