Hi can anyone help me solving this recursion discrete math question?

asked Oct 18, 2017 in Other Math Topics by kate98

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:

To avoid this verification in future, please log in or register.

1 Answer

If n=1 f(1)=2-7+2f(0)=-5+14=9.

f(2)=4-7+18=-3+18=15.

f(3)=6-7+30=29.

f(4)=8-7+58=59.

f(5)=10-7+118=121.

f(n)=2n-7+2f(n-1)=-7+2(n+f(n-1)). The factor of 2 operates with each successive evaluation of f(n), so 2ⁿ is going to be applied. 

f(1)=2×1-7+2f(0)=2×1-7+2×7=2+7.

Since we are looking for a formula for n≥0, f(0) is the first term in the series. Since f(0)=7, we can expect 7 to be a constant term in the formula, and the remaining part of the formula to contain the factor n.

If we look at the series: 7, 9, 15, 29, 59, 121 and take the differences between consecutive pairs we get:

2, 6, 14, 30, 62

If we take half of these we get:

1, 3, 7, 15, 31 which can be represented by 2ⁿ-1. Therefore doubling gives 2(2ⁿ​-1). And f(n)-f(n-1)=2(2ⁿ​-1), so f(n)=f(n-1)+2(2ⁿ​-1). 

f(n-1)+2(2ⁿ​-1)=2n-7+2f(n-1) from which

f(n-1)=2(2ⁿ​-1)-2n+7, therefore f(n)=2(2ⁿ​-1)-2n+7+2(2ⁿ​-1)=4(2ⁿ​-1)-2n+7.

Check formula for n=0 to 5:

f(0)=7, f(1)=9, f(2)=15, f(3)=29, f(4)=59, f(5)=121. The formula in the question doesn’t generate the correct series. So f(n)=4(2ⁿ​-1)-2n+7.
 

answered Oct 18, 2017 by Rod Top Rated User (501,520 points)
You can attach a picture in the comment if that's convenient

Thanks kate98, I realised that the formula in the question seems to be wrong, so I decided to take a different approach. Induction wouldn’t work with an incorrect formula anyway. The formula I came up with can be presented in different ways, but I left it as it is because it’s easy to use it to calculate values for various values of n.

Related questions

Welcome to MathHomeworkAnswers.org, where students, teachers and math enthusiasts can ask and answer any math question. Get help and answers to any math problem including algebra, trigonometry, geometry, calculus, trigonometry, fractions, solving expression, simplifying expressions and more. Get answers to math questions. Help is always 100% free!
80,290 questions
84,162 answers
2,067 comments
67,179 users