为什么下面两个函数会等价？

Question

几个例子

f(3) = 3
f(1) = 3
f(4) = 5
f(2) = 5

一个 typescript 实现是

function gen(n: number): number {
  function f(n: number): number {
    if (n === 2) {
      return n
    }
    return f(n - 1) * 2 - 1
  }

  if (n < 0) {
    throw new Error()
  }
  return f(n + 3)
}

function gen2(n: number): number {
  return Math.pow(2, n + 1) + 1
}

它们在输入相同的情况下结果也是相同的，感觉有点奇怪。。。

---

看起来和等比数列推导有关，不过已经全还回去了 xd

Answer 1

首先有一个推导公式
2 ** 0 + 2 ** 1 + ... + 2 ** (n - 1) == 2 ** n - 1

再已知 sn = s(n-1) * 2，那么
s1 = 2
s2 = s1 * 2 - 1 
   = 2 ** 2 - 1 
   = 2 ** 2 - 2 ** 0
s3 = s2 * 2 - 1 
   = 2 ** 3 - 2 ** 1 - 2 ** 0
s4 = s3 * 2 - 1 
   = 2 ** 4 - 2 ** 2 - 2 ** 1 - 2 ** 0
s4 = s4 * 2 - 1 
   = 2 ** 5 - 2 ** 3 - 2 ** 2 - 2 ** 1 - 2 ** 0

由s4推导
s4 = 2 ** 5 - (2 ** 3 + 2 ** 2 + 2 ** 1 + 2 ** 0)
   = 2 ** 5 - (2 ** 4 - 1)
   = 2 ** 5 - 2 ** 4 + 1
   = 2 ** 4 + 1
  
所以 sn = 2 ** n + 1

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。

Answer 2

$$a_{n}=2a_{n-1} -1$$
$$a_{n}-1=2(a_{n-1} -1)$$
所以$$\{a_{n}-1\}$$
是一个首项为2, 公比为2的等比数列, 由等比数列通项公式得
$$a_{n}-1=2 * 2^{n-1}$$
则$$a_{n}=2^n+1$$

Answer 3

对f1进行归纳，可得 f1(n+2)=(2ⁿ﹣¹ +1)X2-1，化简得f1(n+2)=2ⁿ+1 =f2(n);

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。