Explore BrainMass

Explore BrainMass

    Solving a Recurrence Relation

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Solve the following recurrence relation:

    a(n) = a(n-1) + 3(n-1), a(0) = 1

    I know this should not be a difficult problem, but my main problem is in solving the problem when the coefficient of the a(n-1) term is 1. Also, when a summation is in the solution, I do not understand how to convert from a summation to a C(n,k) or a P(n,k). Could you please give a step by step explanation of the process involved with solving this type of problem? Thank you.

    © BrainMass Inc. brainmass.com November 24, 2022, 11:46 am ad1c9bdddf

    Solution Preview

    a(1) = a(0) + 0 = 1

    a(n) = a(n-1) + 3*(n-1).....
    a(n) = a(n-2)+3*(n-2)+ 3*(n-1).....
    a(n)= a(n-3) + 3*(n-3) + 3*(n-2) + 3*(n-1).....

    and so on till u get a(1)...

    So u will have:
    a(n) = a(1) + 3*(1+2+3+4........+n-1)

    Now sum of first k numbers is k(k+1)/2

    with k=n-1 in this case.

    so a(n) = 1 + [3*n(n-1)/2]


    Solution Summary

    A recurrence relation is solved. The solution is detailed.