按 [定理] 结构归纳原理（structural induction） 对 $𝑡$ 进行结构归纳。

• $𝑡$ 是常量：$\mathrm{depth}\left(𝑡\right)=0<1=\mathrm{size}\left(𝑡\right)$。
• $𝑡=\text{ succ }{𝑡}_1$（$\text{pred}$、$\text{iszero}$ 完全相同）： 归纳假设 是 $\mathrm{depth}\left({𝑡}_1\right)<\mathrm{size}\left({𝑡}_1\right)$，两边加一即得 $\mathrm{depth}\left(𝑡\right)<\mathrm{size}\left(𝑡\right)$。

• $𝑡=\text{ if }{𝑡}_1\text{ then }{𝑡}_2\text{ else }{𝑡}_3$：设 ${𝑡}_{𝑖}$ 是三个子项中深度最大的那个。由 归纳假设 ，

  $$\mathrm{depth}\left(𝑡\right)=\mathrm{depth}\left({𝑡}_{𝑖}\right)+1<\mathrm{size}\left({𝑡}_{𝑖}\right)+1\le \mathrm{size}\left({𝑡}_1\right)+\mathrm{size}\left({𝑡}_2\right)+\mathrm{size}\left({𝑡}_3\right)+1=\mathrm{size}\left(𝑡\right)$$

  其中 $\le$ 用到了每个子项的大小都至少为 $1$。