1.

What is the recurrence relation for 1, 7, 31, 127, 499?(a) bn+1=5bn-1+3(b) bn=4bn+7!(c) bn=4bn-1+3(d) bn=bn-1+1This question was addressed to me during an interview for a job.The doubt is from Advanced Counting Techniques in section Counting of Discrete Mathematics

Answer» RIGHT option is (c) bn=4bn-1+3

For explanation: Look at the differences between terms: 1, 7, 31, 124,…. and these are growing by a factor of 4. So, 1⋅4=4, 7⋅4=28, 31⋅4=124, and so on. Note that we always END up with 3 less than the next TERM. So, bn=4bn-1+3 is the recurrence RELATION and the initial CONDITION is b0=1.


Discussion

No Comment Found

Related InterviewSolutions