Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.