The function f : N → N is defined by f(0) = 7, f(n) = 2n − 7 + 2 · f(n − 1) if n ≥ 1. • Determine f(n) for n = 0, 1, 2, 3, 4, 5. • Prove that f(n) = n · 2 n + 7 for all integers n ≥ 0.

Question

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

Answer 1

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.
 

Comments

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.