3
$\begingroup$

We have $k$ around $10^6 - 10^7$. I need to compute value of the sum

$ S(k)=\sum_{n=0}^{\lfloor k/2 \rfloor}\frac{(k-n)!}{(k-2n)!n!} $

modulo $2462$. It seems that if a term has factors $2,1231$ (i.e. factors of $2462$) I can simply drop it but are there other tricks I could deploy in computing the value?

This is a stuck point from an assignment I found on internet which I'm working on to (re-)learn C and gain some understanding on algorithms. I would prefer some pointers instead of a solution. I feel confident that the sum could be simplified and there is something on modulo algebra I could use but I can't spot what I should try next.

1 Answers 1

4

This is actually a famous identity on binomial coefficients. Note that $\frac{(k-n)!}{(k-2n)!n!} = \binom {k-n}{n}$, and then your sum is $\sum_{n=0}^{\lfloor \frac{k}{2} \rfloor} \binom {k-n}{n}$. This is the sum of the diagonals of Pascal's triangle, and has a nice solution in terms of Fibonacci numbers.