let nCk denote the binomial coefficient and F[m] be the mth fibonaki number given by F[1]=F[2]=1 and F[m+2]=F[m]+F[m+1] for
m≥1.Show that
∩(nCk)=F[m+1] for all m≥1.
where n≥k≥0 and n+k=m
-
UP 0 DOWN 0 0 1
1 Answers
2305I think you meant Σ nCk.
I have done this problem through bijection and is quite complicated.So please tell me if there is an easier and less complicated solution to this.
Let us consider a set S = {1,2,3,....,n}
Let an be the number of subsets of S having no consecutive numbers.
Let us write 1 if the subset contains the number and 0 if the subset does not contain the number.
Eg: For the set A = {1,2,3}
i)The subset 101 will be {1,3}
Here the first 1 implies that it contains 1
The 0 implies that there is no 2
The 3rd digit 1 implies that the subset contains 3.
ii)Similarly the subset 110 will be {1,2)
Let us try to find a3
The subsets not containing consecutive integers are {},{1},{2},{3},{1,3}
Hence a3 = 5
Converting these to binary we get 000,100,010,001,101.
Observe that the binary numbers do not have consecutive 1's (otherwise it must contain consecutive integers which is not possible).
We try to derive a recursive form for an.
Now an can have a 0 in the beginning.In that case the rest binary numbers can be written in an-1 ways.
If an has a 1 in the beginning.It must have a 0 after that since there can be no consecutive integers.The rest can be done in an-2 ways.
Hence an=an-1+an-2.
Given a1=2 and a2=3.
an is the fibonacci term Fn+2.
This gives us our RHS.
Now for the LHS.
Number of ways of forming a subset of S having non consecutive elements and having 0 terms is= 1
(Since the only such possible subset is {} )
Number of ways of forming a subset of S having non consecutive elements and having 1 terms is= n
(These are {1},{2},{3},{4},....{n} )
1 = n+1C0 and n = nC1
We conjecture that the number of ways of forming a subset of S having non consecutive elements and having i terms is = n+1-iCi .
Let us try to prove this by induction.
I hope the initial case can be done by all.
I assume that the statement is true for i=k.
Let us try to find the number of ways of forming a subset of S having non consecutive elements and having k+1 terms.
If the subset contains 1 it must not contain 2.
Hence the number of ways of forming non consecutive subsets containing 1 and having k+1 elements is equal to
the number of ways of forming non consecutive subsets having k elements of the set:
{3,4,5,....n} which is = n-k-1Ck.
If the subset contains 2 it must not contain 3.
Furthermore it should not contain 1 since we already taken that case.
Hence the number of ways of forming non consecutive subsets containing 2 is equal to the number of ways
of forming non consecutive subsets having k elements of the set:
{4,5,6,....n} which is = n-k-2Ck.
Similarly on going on like thiswe find that the number of ways of forming a subset of S having non consecutive elements and having k+1 terms =
n-k-1Ck.+n-k-2Ck+1+n-k-3Ck.+....+kCk which is indeed equal to
n-kCk+1 = n+1-(k+1)Ck+1.
Hence we have proved it by induction.
Therfore the number of ways of forming a subset of S having non consecutive elements = n+1C0 + nC1+n-1C2....= Σ mCk where
m+k = n+1.
This gives us our LHS.
Hence Σ mCk = F[n+2]
where m+k = n+1.
or,
Σ mCk = F[n+1]
where m+k = n.