Algorithm to Sum The Fibonacci Numbers

  • 时间:2020-09-07 12:13:31
  • 分类:网络文摘
  • 阅读:102 次

The Fibonacci numbers are defined as the following sequence, with the current item is the sum of the previous two items.

F(1) = 0
F(2) = 1
F(N) = F(N – 1) + F(N – 2) for N >= 3

latex-fibonacci Algorithm to Sum The Fibonacci Numbers algorithms javascript math

Fibonacci Equation

The first few Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21…

Of course, it is trivial to write a loop to sum the Fibonacci numbers of first N items.

1
2
3
4
5
6
7
8
9
10
11
12
function sumOfFib(n) {
  let a = 0;
  let b = 1;
  let sum = 0;
  for (let i = 1; i < n; ++ i) {
     let c = a + b;
     a = b;
     b = c;
     sum += a;
  }
  return sum;
}
function sumOfFib(n) {
  let a = 0;
  let b = 1;
  let sum = 0;
  for (let i = 1; i < n; ++ i) {
     let c = a + b;
     a = b;
     b = c;
     sum += a;
  }
  return sum;
}

Let’s define the S function the sum of first few Fibonacci numbers:

S(1) = F(1) = 0
S(2) = F(1) + F(2) = 1
S(3) = F(1) + F(2) + F(3) = 2
S(4) = F(1) + F(2) + F(3) + F(4) = 4
S(5) = F(1) + F(2) + F(3) + F(4) + F(5) = 7

We notice that
tex_882caded33c9e36a815c7993cab7dd7e Algorithm to Sum The Fibonacci Numbers algorithms javascript math

For example:
S(4) = F(6) – 1 = 5 – 1 = 4
S(3) = F(5) – 1 = 3 – 1 = 2

Using Induction to Prove the Fibonancci Sum Formula

S(1) = 0
S(2) = 1
Assume S(N) = F(N+2) – 1 stands.
S(N+1) = S(N) + F(N+1)
= F(N+2) + F(N+1) – 1
= F(N+3) – 1
And it also works for N+1!

Cancel Out the Fibonacci Numbers

We can rewrite the Fibonacci Formula as F(N) = F(N + 2) – F(N + 1).
Therefore, tex_5b0d46d6ed6c9aa9118a4410e5e8db3a Algorithm to Sum The Fibonacci Numbers algorithms javascript math
= F(2) – F(1) + F(3) – F(2) + F(4) – F(3) + …. F(N + 2) – F(N + 1)
Intermediate items are canceled out:
= F(N + 2) – F(1) = F(N + 2) – 1
How cool is that!

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
只有这样吃大蒜才能杀菌防癌,以前你吃对了吗  丝瓜营养丰富,其对人体的保健功效如此之多  患有胃病的人常吃这些食物,可以帮助调理好胃  山药营养丰富食疗价值高,助爱美女性吃出好身材  糖尿病患者常有这些饮食误区,朋友们注意啦!  网络上流传甚广的垃圾食品方便面有毒、致癌的传闻是真的吗?  经常吃核桃仁可以补脑是真的吗 一天吃多少核桃才健康  甘蓝汁食疗方法对胃病患者非常有益 疗效甚至超过单纯药物  面部出现这些变化则是男人肾虚要进行饮食调理  酱油吃多了会导致皮肤变黑吗?别再被忽悠啦! 
评论列表
添加评论