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
add comment

1 Answer

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
    
This looks exactly what I was looking for. Let me try an implementation before marking an answer :) Thank you! –  rank Nov 26 '12 at 7:40
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.