Please Help to find nCr

help
1

I need to find sum of first k term of nCr when n is in fibonaccci and r is constant.

for eg. 2C2 + 3C2 + 5C2 + 8C2 + . . . . . (till Kth term). where k is given.

The maximum value of k can be until 10^18 so loop will not work. any formula or O(logn) complexity algorithm will only work.

Can anyone please help. @vijju123 @waqar_ahmad224 @taran_1407 @galencolin @carre

1 Like
2

I’m assuming r=2, and r cannot go beyond 2 since according to your example, fibonacci starts from 2.

Take a=2, b=3, sum=a*(a-1) + b*(b-1)

From i=3 to k{
c=a+b
sum+= c*(c-1)
a=b
b=c
}

Print sum/2

Logic: nC2 = n*(n-1)/2

3

The maximum value of k can be until 10^18 so loop will not work. any formula or O(logn) complexity algorithm will only work.

4

Okay. You should’ve provided the constraints along with the question…

5

#include
using namespace std;
int fact(int n)
{
int fact=1;
for(int i=2;i<=n;i++)
{
fact=fact*i;
}
return fact;
}
int main()
{
int n;
cin>>n>>r;
int ans=fact(n)/fact(r)*fact(n-r);
cout<<ans<<endl;
return 0;
}

7

I don’t think this solution will work!! Please read the question carefully bro!!

8

For the sake of explaining, I will denote i_{th} Fibonacci number as F_i. Notice that the sum

{{F_2}\choose{2}} + {{F_3}\choose{2}} + ... + {{F_n}\choose{2}}

can be rephrased as \sum_{i = 2}^{n}{F_i\choose{2}} which is same as saying

{\sum_{i = 2}^{n}{\frac{(F_i)(F_i - 1)}{2}}} = {\sum_{i = 2}^{n}{\frac{({F_i}^2 - F_i)}{2}}}

There is not easy way to solve this, right? Well, actually notice the following property:

{\sum_{i = 1}^{n}{F_i^2}} = F_n \cdot F_{n + 1}

This can easily be proven by induction:

Basis of induction:

For P(1), sum is obviously F_1 \cdot F_2 = 1 \cdot 1 = 1, which is true.

Inductive Hypothesis

If P(n) hold, then P(n + 1) holds as well.

Inductive Step

{\sum_{i = 1}^{n}{F_i^2}} = F_n \cdot F_{n + 1} holds.

We need to show

{\sum_{i = 1}^{n + 1}{F_i^2}} = F_{n + 1} \cdot F_{n + 2}

We can reformulate the sum as

{\sum_{i = 1}^{n + 1}{F_i^2}} = {\sum_{i = 1}^{n}{F_i^2}} + F_{n + 1}^2

This is equivalent to:

{F_n \cdot F_{n + 1}} + F_{n + 1}^2 = F_{n + 1} \cdot (F_n + F_{n + 1}) = F_{n + 1} \cdot F_{n + 2}

Hence the above statement is proved.

Another observation to make is that \sum_{i = 1}^{n}{F_i} = F_{n + 2} - 1. Again this can be easily proven using induction so I leave it as an exercise to you.

Now that we have these out of our way, we can rephrase the original problem as finding the value of:

{\sum_{i = 2}^{n}{\frac{({F_i}^2 - F_i)}{2}}} = {{\frac{1}{2}}({\sum_{i = 2}^{n}{F_i^2}} - {\sum_{i = 2}^{n}{F_i}})} = {{\frac{1}{2}}{(F_n \cdot F_{n + 1} - 1 - (F_{n + 2} - 1 - F_1))}}

Thus the original problem is reduced to efficiently calculating n_{th} and (n + 1)_{th} Fibonacci number (this allows us to easily compute F_{n + 2} as well).

This is a well-known problem and is most commonly seen matrix exponentiation introductory problem, so you can read about it on GFG or some other online source. Hope I could help! :slight_smile:

EDIT: I apologize for making many small mistakes while writing this, the +1 and +2 things should be fixed now.

2 Likes
9

@nichke you are only considering r = 2 , but r can be any constants IMO
btw your explanation is too good :slight_smile:

10

Thanks for the compliment.

I honestly don’t know what values r can take. I took the brief description that was provided here, OP didn’t complain about r being 2 in the answer @bal_95 provided, so I stuck with that. I don’t think it’s even possible to solve this problem for any k, but I may as well be wrong as some 6* or 7* user could possibly come up with an optimal solution.

11

if the maximum value of K is 10^18 so output must be modulo of some number.
hope this link will help —> Binomial Coefficients