I think that for the case k=1 you need to show that, if prime p divides Fibonacci(p-1), the following holds true: if m!=n (mod p) then Fibonacci(m)!=Fibonacci(n) (mod p).
QuoteOriginally posted by: PenielAny hint Chukchi?Sure, Peniel. For k = 1 there is a nice formula found by Vladeta Javovic:Sum[ Sum[ Fibonacci[i+j-1], {i,1,n} ], {j,1,n} ] = Fibonacci(2*n+3) - 2*Fibonacci(n+3) + 2.Ref. http://www.research.att.com/~njas/sequences/A120297
Peniel,May be the following fact would help a little:If prime p divides Fib(p-1) then p divides Fib(p)-1 too, and also if prime p>2 divides Fib(p)-1 then p divides Fib(p-1) too.
Here is a hint for k = 2:If I'm not mistaken there is a nice formula for our Sum when k = 2.Something like:Sum( (Fibonacci(i+j-1))^2, {i,1,p-1}, {j,1,p-1} ) = L(2(p-1))*(F(p-1))^2,where L(i) is a Lucas Number L(i) = F(i-1) + F(i+1)