Clarification in the proof for the Bellamn-Ford algorithm
The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion.


  The correct claim is the following: Consider the values of
  $\text{dist}[\cdot]$ computed at the end of the $k$-th iteration of
  Bellman-Ford. For any vertex $u$, let $d^{(k)}_u$ be the length of the
  shortest path from $s$ to $u$ that uses at most $k$ edges (if no such path exists then $d^{(k)}_u = +\infty$). It holds
  that $\text{dist}[u]\le d^{(k)}_u$.


Notice the $\le$ sign!

The above claim implies that, after the $(n-1)$-th iteration all distances stored in $\text{dist}[\cdot]$ are smaller than or equal to the true distances in the graph.

Clearly, it also holds that all the distances stored in $\text{dist}[\cdot]$ are larger than or equal to the true distances in the graph (since every time you a distance is updated, the new distance is always the length of some path from $s$).

Combining the previous two properties, you can conclude that $\text{dist}[\cdot]$ stores the exact distances from $s$, i.e., that the Bellman-Ford algorithm is correct.



Let me prove my claim formally. To avoid confusion this is the pseudocode of the Bellman-Ford algorithm I will be using:

Bellman-Ford(G=(V,E; w), s):
  For u in V:
    dist[u]=+infinity

  dist[s]=0
  For k=1,..., n-1:
    For (v,u) in E:
      dist[u] = min(dist[u], dist[v] + w(v,u))


The proof is by induction on $k=0, \dots, n-1$ (where the end of the $0$-th iteration corresponds to the state of the algorithm just before the first iteration of the outer for loop).

The base case is $k=0$. There is only one vertex $u$ such that the path from $s$ to $u$ uses $k=0$ edges, namely $u=s$. The claim holds for $s$ since $\text{dist}[s] = 0 = d_s^{u}$. For $u \neq s$, the claim holds since $\text{dist}[u] = +\infty = d_u^{(k)}$.

Suppose now that the claim holds for $k-1 \ge 0$. We will prove that it also holds for $k$. Consider any vertex $u \in V$, let $P$ be the shortest path from $s$ to $u$ that uses at most $k$ edges, let $w(P)$ be the (weighted) length of $P$, and let $|P|$ denote the number of edges of $P$. We distinguish two cases:

If $|P| &lt; k$ then $d_u^{(k)} = d_u^{(k-1)}$ and, by inductive hypothesis, at the end of the $(k-1)$-th iteration of the outer for loop we had $\text{dist}[u] \le d_u^{(k-1)} = d_u^{(k)}$. The claim follows since the values of $\text{dist}[\cdot]$ never increase during the execution of the algorithm.

If $|P|=k$ then $|P| \ge 1$. Let $(v,u)$ be the last edge of $P$ and let $P'$ be the subpath of $P$ from $s$ to $v$. 
Let $\delta$ be the value of $\text{dist}[v]$ at the end of the $(k-1)$-th iteration of the outer for loop.
By the suboptimality of shortest paths we know that the (weighted) length $w(P')$ of $P'$ is exactly $d_v^{(k-1)}$. Moreover, the inductive hypothesis ensures that $\delta \le d_v^{(k-1)}$. 
Consider the situation at end of the iteration of the inner for loop that considers edge $(v,u)$, during the $k$-th iteration of the outer for loop. Since values of $\text{dist}[\cdot]$ never increase, we must have:
$$
\begin{align*}
\text{dist}[u] &amp;\le \text{dist}[v] + w(v,u) \\
&amp;\le \delta + w(v,u) \\
&amp;\le d_v^{(k-1)} + w(w,v) \\
&amp;= w(P') + w(v,u) = w(P) = d_u^{k}.
\end{align*}
$$
Once again, since the values of $\text{dist}[\cdot]$ never increase, the above inequality must also hold true at the end of the $k$-th iteration of the outer for loop.