Recurrence Relations

[proff.hacker]

1- for each of the following sequences. find a recurrence relation satisfied by this sequence.(the answers are not unique since there are infinitely many different recurrence relations staisfied by any sequence.)
a- an=3
b- an=2n
c- an=2n+3


2- an employee joined a company in 1987 with a starting salary of $50,000. Every year this employee receives a raise of $1000 plus 5% of the salary of the previous year.
a) Set up a recurrence relation for the salary of this employee n years after 1987.
b) what is the salary of this employee in 1995?

3- find a recurrence relation for the number of permutations of a set with n elements.

4- Find a recurrence relation for the number of bit sequences of length n with an even numbers of 0s.

any help please.

[DerFarm]

If you can't do the homework, don't take the course.

[DavidHooper]

Well I assume an is a-subscript-n. I write a(n). You can work out question a - it hardly counts as a recurrence relation.

b) a(n) = 2n gives a(n) = a(n-1) + 2 with a(1) = 2
c) a(n) = 2n + 3 gives a(n) = a(n-1) + 2 with a(1) = 5