Use induction to prove the correctness of shortest path algorithm

Question

Suppose given a directed graph $G=(V,E)$ with positive weights and we try to find shortest path $d(s,t,\ell)$ from $s$ to $t$ such that we traverse at most $\ell$ edges ($\ell$ is even). Let $w(u,v)$ be weight of edge (u,v), so we use this recurrence, $$d(s,t,\ell)=\begin{cases} \min_{x \in V}\{d(s,x,\frac{\ell}{2})+d(x,t,\frac{\ell}{2})\},& \text{if } \ell\geq 2\\ w(s,t), & \ell=1\\ \infty, & \ell=0 \end{cases} $$

How we can prove by induction that the above recurrence find optimal solution?

I try to induction on $\ell$ so when we let $\ell=0$ the answer is $\infty$ so it's correct. Also for $\ell=1$ the correct answer is $w(s,t)$ so the recurrence is correct, but how we can extend this idea to show that whole recurrence is correct?

Answer 1

Here is how a proof by induction would look like here. We prove by induction on $r$ the following claim:

For every pair of vertices $s,t$, the value of $d(s,t,2^r)$ is the length of the shortest path from $s$ to $t$ which uses at most $2^r$ edges (or $\infty$ when there is no such path).

Denote this claim by $P(r)$. You need to prove two things:

1. Basis: $P(0)$ holds.
2. Step: If $P(r)$ holds then $P(r+1)$ holds.

If the proof doesn't work, perhaps you need to modify your recurrence. In case this modification involves allowing lengths which are not powers of $2$, you might need to prove the following similar claim by induction on $\ell$:

For every pair of vertices $s,t$, the value of $d(s,t,\ell)$ is the length of the shortest path from $s$ to $t$ which uses at most $\ell$ edges (or $\infty$ when there is no such path).

Denoting this claim by $Q(\ell)$, the proof by induction would go as follows:

1. Basis: $Q(0)$ and $Q(1)$ holds.
2. Step: If $Q(r)$ holds for all $r < \ell$, then $Q(\ell)$ also holds.

Good luck!