I have to compute (m+n)!/(m!)(n!) where m>=n.
Due to overflow constraints, I cannot calculate (m+n)! as it might exceed size of variable (int). To overcome this difficulty, one solution is to do the following :
Observe that the original problem can be reduced to (m+1)(m+2)...(m+n)/(n!)
We do the following :
integer result = 1, j=1;
for(integer i = m+1; i <= m+n; i++)
{
result = result * i;
result = result / j;
j=j+1; }
return result;
I do understand that a sequence of k consecutive integers will consist of a multiple of k (periodicity), but situation above isn't that straight forward. Since we are also dividing at each step, how do I show that although the resulting product is no longer a product of "consecutive" integers, we can still divide in this iteration by j.
Crude example, let sequence be 39,40,41,42,43. Here division by 2 utilises 40, so does 4, and 5 (in their respective iterations), but after division by 2, product is no longer of consecutive integers - why "division by 2" is not affecting "division by 4" despite both utilising integer 40.
So you want to prove that each step of your algorithm produces an integer, i.e. the prefix products $\prod_{i=1}^k \frac{m + i}{i}$ is an integer for all $k = 1, 2, \ldots, n$ (we will just prove it for all $k$). This is true because, well, $\prod_{i=1}^k \frac{m+i}{i} = \frac{(m+k)!}{m!k!}=\binom{m+k}{k}$, which is an integer. See this for a proof.