●●● ●●●● ●●●●● ●●●● ●●0●● Recurrence relations ●●●● ●●●● o The interview question from Google To reach the nth stage, there are two possibilities First reach the(n-2)th stage, then go to the nth stage directly First reach the(n-1)th stage, then go to the nth stage We can have the following recurrence relation ●an=an+a, n-2 a1=1,a,=29 Recurrence Relations ⚫ The interview question from Google ⚫ To reach the nth stage, there are two possibilities: ⚫ First reach the (n-2)th stage, then go to the nth stage directly ⚫ First reach the (n-1)th stage, then go to the nth stage ⚫ We can have the following recurrence relation: ⚫ an = an-1 + an-2 ⚫ a1 = 1, a2 = 2