SPOJ.com - Problem CLASSICSEQ

CLASSICSEQ - Classic Sequence Sum

#math-number-theory #matrixexpo

Find the value of sum of square of all the first N numbers in Fibonacci series.

First line of every input test file contains T denoting the number of test cases for the file, followed by T numbers N.

For every number N output the result( sum of square of first N Fibonacci numbers) in the below described format.

Value can overflow the standard data type, output the result modulo 1000000007 (10⁹ + 7).

1 <= T <= 10000 (10⁴)

1 <= N <= 1000000000000000000 (10¹⁸)

Input:
3
1
5
10

Output:
Case 1: 1
Case 2: 40
Case 3: 4895



	amitroy3370: 2022-10-09 17:44:26 we know that, for all the real number of n, sum(j = 1 to n) f(j^2) = f(n) * f(n + 1) basis for the introduction: ........................... we know that f(1)^2 = 1 = f(3) - 1 from(j = 1 to 1) f(j)^2 = f(1)^2 = 1 * 1 = 1 = f(1) * f(2) from the rules of the induction hypothesis: ........................................... sum(i = 1 to k) f(i)^2 = f(k) * f(k + 1) so we need to chow that the sum(i = 1 to k + 1) f(i)^2 = f(k + 1) * f(k + 2) induction step: ............... sum(i = 1 to k + 1) f(i)^2 = sum(i = 1 to k)f(i)^2 + f(k + 1)^2 = f(k) * f(k + 1) + f(k + 1)^2 = f(k + 1) * (f(k) + f(k + 1)) = f(k + 1) * f(k + 2) so can say that p(k) => p(k + 1) so all number from 1 to n, f(n)^2 = f(n) * f(n + 1) Last edit: 2022-10-10 19:23:01
	Simes: 2022-10-04 11:29:49 Apparently, the square of Fibonacci numbers from 1 to n is equal to the nth Fibonacci number multiplied by the n+1 th Fibonacci number. So the problem then becomes being able to calculate the appropriate terms of the Fibonacci sequence, and I think matrix multiplication may be used here.
	amitroy3370: 2022-10-04 06:55:23 Can I get some of the hint to solve this problem?
	atu1_rana: 2018-10-20 19:21:59 Thanks [Lakshman] for suggesting right place.
	[Lakshman]: 2018-10-20 18:14:06 I don't think this problem is relevant to the classical section. Should be moved to Tutorials Last edit: 2018-10-20 20:35:37