Information
- ID
- 223
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 10
- Tags
- # Submissions
- 3
- Accepted
- 2
- Uploaded By
记 fi 为斐波那契数列第 n 项,si 为斐波那契数列前 n 项和。
引理 1:对于任意 i,有 si=fi+1+fi−1。
证明:i=1 时,si=fi+1+fi−1 成立。
对于任意 i,如果 si=fi+1+fi−1 成立,那么有 si+1=2fi+1+fi−1。因为 fi+2=fi+1+fi,所以 si+1=fi+2+fi+1−1。令 j=i+1,则对于 j,sj=fj+1+fj−1 成立。
那么可以得到,对于任意 i,都有 si=fi+1+fi−1。证毕。
然后本题利用上一题的方法即可。
By signing up a HFOJ universal account, you can submit code and join discussions in all online judging services provided by us.