設

• f[n] = 長度為 n 的路徑圖 (Pₙ) 的極大獨立集個數。

分析第一個點 (編號 1) 的情況：

• 情況 1：選點 1

  • 那麼點 2 不能選，剩下是長度 n-2 的路徑

  • 但要注意，因為點 1 被選了，點 2 就被覆蓋，沒問題

  • 所以這時相當於求 f[n-2]

• 情況 2：不選點 1

  • 那麼為了滿足「極大」條件，點 2 必須被選（否則點 1 就可以再加進集合）

  • 所以其實點 2 一定選，然後點 3 不能選，剩下長度 n-3 的路徑

  • 這對應 f[n-3]

所以得到遞迴：

f[n]=f[n−2]+f[n−3],  n≥4