Solving Linear Recurrence for Programming Contest


This is a doubt from this forum(Solving Linear Recurrence for Programming Contest)–

LINK==
http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

What is ’ c ’ in here ?

They are specific coefficients for the given recurrence. for example, the fibonacci series is

f(n) = f(n-1) + f(n-2)… here there will be two coefficients (the 'c’s in the link) because nth term depends upon two terms, (n-1)th and(n-2)th terms. and for this series c1 and c2 are 1 and 1 respectively.

You could have other recurrences as well like f(n) = c1*f(n-1) + c2*f(n-2) + … and so on.

1 Like