Search code examples
recurrence

how to solve the recurrence T(n)=T(n-1)+T(n-3)-T(n-4), n>=4

How to solve the recurrence equation

1.T(n)=T(n-1)+T(n-3)-T(n-4), n>=4

2.subject to T(n)=n for 0<=n<=3

Solution

  • From calculating the first numbers you can quickly suspect that the solution is T(n) = n.

    You can then prove this using mathematical induction:

    Basis:

    For the first element, n = 4, we can calculate the value like:

    T(4) = T(3) + T(1) - T(0) = 3 + 1 - 0 = 4

    so the statement is true.

    Inductive step:

    Assuming T(n) = n, show that T(n+1) = n+1:

    T(n+1) = T(n) + T(n-2) - T(n-3) = n + (n-2) - (n-3) = n+1

    which shows T(n) = n for all n >= 0.