Ask Question
30 October, 09:07

Solve the following recurrence relations. a. x (n) = x (n - 1) + 5 for n > 1, x (1) = 0b. x (n) = 3x (n - 1) for n > 1, x (1) = 4c. x (n) = x (n - 1) + n for n > 0, x (0) = 0

+3
Answers (1)
  1. 30 October, 09:30
    0
    (a) x (n) = 5 (n-1)

    (b) x (n) = 4 X 3ⁿ⁻¹

    (c) x (n) = n (n+1) / 2

    Step-by-step explanation:

    (a) x (n) = x (n - 1) + 5 for n > 1, x (1) = 0

    Put n=n-1

    x (n-1) = x (n-2) + 5

    Recall: x (n-1) = x (n) - 5

    Substitute:

    x (n) - 5=x (n-2) + 5

    x (n) = x (n-2) + 5+5

    Put n=n-2

    x (n-2) = x (n-3) + 5

    Recall: x (n-2) = x (n) - 5-5

    Substitute:

    x (n) - 5-5=x (n-3) + 5

    x (n) = x (n-3) + 5+5+5

    Generalising

    x (n) = x (n-i) + 5i for i
    Put i=n-1

    x (n) = x (n - (n-1)) + 5 (n-1)

    x (n) = x (1) + 5 (n-1) = 0+5 (n-1)

    x (n) = 5 (n-1)

    (b) x (n) = 3x (n - 1) for n > 1, x (1) = 4

    Put n=n-1

    x (n-1) = 3x (n-2)

    Recall: x (n-1) = x (n) / 3

    Substitute:

    x (n) / 3=3x (n-2)

    x (n) = 3 X 3x (n-2)

    Put n=n-2

    x (n-2) = 3x (n-3)

    Recall: x (n-2) = x (n) / 3²

    Substitute:

    x (n) / 3²=3x (n-3)

    x (n) = 3³x (n-3)

    Generalising

    x (n) = 3ⁱ x (n-i) for i
    Put i=n-1

    x (n) = 3ⁿ⁻¹ x (n - (n-1))

    x (n) = 3ⁿ⁻¹ x (1)

    x (n) = 3ⁿ⁻¹*4

    x (n) = 4 X 3ⁿ⁻¹

    (c) x (n) = x (n - 1) + n for n > 0, x (0) = 0

    Put n=1

    x (1) = x (1-1) + 1

    x (1) = 0+1=1

    Put n=2

    x (2) = x (2-1) + 2

    x (2) = x (1) + 2=1+2=3

    Put n=3

    x (3) = x (3-1) + 3=x (2) + 3=3+3=6

    Generalising

    x (n) = n (n+1) / 2
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Solve the following recurrence relations. a. x (n) = x (n - 1) + 5 for n > 1, x (1) = 0b. x (n) = 3x (n - 1) for n > 1, x (1) = 4c. x (n) = ...” in 📗 Mathematics if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers