AoPS Academy
![$f : [0,1] \longrightarrow \mathbb{R}$](http://latex.artofproblemsolving.com/9/a/4/9a4b7997c35990f839742d29866122791ade8b7c.png)
is differentiable with 
. If 
for all ![$x \in [0,1]$](http://latex.artofproblemsolving.com/d/3/4/d3423a3200d0ad7660fc4265d59d5598a53d551d.png)
, then show that 
for all 
.
over all triples 
of distinct real numbers such that
is a finite set, let denote the number of elements in . Call an ordered pair 
of subsets of 
if 
for each 
, and 
for each 
. How many admissible ordered pairs of subsets 
are there? Prove your answer.
is a finite set, let denote the number of elements in . Call an ordered pair of subsets of if for each , and for each . How many admissible ordered pairs of subsets are there? Prove your answer.
where 
denotes the Fibonacci sequence, with 
and 
. For some 
, by summing over 
and 
, it is clear that there are
ways to choose 
and 
. Thus consider the formal series
Then, we have
where 
and 
are the roots of 
. By the geometric series formula it follows that 
.
and 
, so we have
as desired. 
We sum this by parts according to 
. Eaach of these parts is equal to 
Here 
and 
. This is just the 
coefficient in 
Expanding out the series for this, the desired coefficient is 
. Hence, the answer is 
and are 
and 
respectively, we find we need to choose numbers from 
numbers to fill set and numbers from 
numbers to fill set . Thus we have 
choices for and 
choices for . Note we have the added restriction that 
, else the binomial coefficients are undefined.
Then we will use snake oil. The idea is to let 
, and consider the generating function,
Now by substituting 
we find,
Now we find,
This then simplifies to,
Which in turn becomes,
where we take 
and 
. Then we can use geometric series to find,
Now we want to find the coefficient of 
. Thus the coefficient of is,
, 
.
for each 
, is a subset of 
(
if 
).
These are 
questions in total.
2's and 
1's.
These are 
questions in total.
2's and 1's.
2's and 
1's, which sum to 
.. must have an odd number of 1's, and the middle 1 is the separator. and can be determined, and the two sets can be uniquely recovered.
by using partial fractions and then comparing with the formula of Fibonacci numbers.
, where 
denotes the th Fibonacci number.![\[S_{n} = \sum_{A \geq 0}\sum_{B \geq 0} \binom{n - B}{A} \binom{n - A}{B}\]](http://latex.artofproblemsolving.com/d/c/9/dc9df6659ce077dccdaadd74111c9b6b724bb839.png)
and 
, deriving a closed form for this given and , and sum over all possible pairs of and . Note that for valid elements of set , we must choose elements that are NOT in the range 
to ; thus, there are 
combinations. The same logic holds for choosing elements from set . Since these selections are independent, we multiply these to obtain the result![\[\binom{n - B}{A}\binom{n - A}{B}\]](http://latex.artofproblemsolving.com/6/e/e/6eeca201ea388918aa768fc59c27fa73a0583e5d.png)
, we use generating functions. Define 
to be![\[F(x) = \sum_{n \geq 0} S_{n} x^n \]](http://latex.artofproblemsolving.com/b/e/0/be0f26d9cd03fb67ea7132dcc54ebe3d0222ffe8.png)
![\[F(x) = \sum_{n \geq 0} \sum_{A \geq 0}\sum_{B \geq 0} \binom{n - B}{A} \binom{n - A}{B} x^n\]](http://latex.artofproblemsolving.com/b/1/7/b17eb5eb9dc516df6b0f397e0aea35d0935acd55.png)
to obtain![\[F(x) = \sum_{A \geq 0} \sum_{B \geq 0}\sum_{n \geq 0} \binom{n + A}{A} \binom{n + B}{B} x^{A + B + n}\]](http://latex.artofproblemsolving.com/b/0/7/b075be07acfa23f55afce3df46c81f8f9fe0a1c5.png)
![\[F(x) = \sum_{n \geq 0} x^{n} \sum_{B \geq 0} \binom{n + B}{B} x^{B} \sum_{A \geq 0} \binom{n + A}{A} x^{A}\]](http://latex.artofproblemsolving.com/3/7/e/37ed4f6ebe5630501f7034235309a73e60424720.png)
![\[F(x) = \sum_{n \geq 0} x^{n} \left( \sum_{A \geq 0} \binom{n + A}{A} x^{A} \right)^2 \]](http://latex.artofproblemsolving.com/d/9/6/d9624ea79f8fff1b9d9252acaf910d7a55522b77.png)
![\[F(x) = \sum_{n \geq 0} x^{n} \left( \frac{1}{(1 - x)^{n + 1}} \right)^2 \]](http://latex.artofproblemsolving.com/b/6/2/b6210bad86dd7dc403873c0daa2d130ad147c6cb.png)
![\[F(x) = \frac{1}{(1 - x)^2} \sum_{n \geq 0} \left( \frac{x}{(1 - x)^{2}} \right)^n \]](http://latex.artofproblemsolving.com/d/3/4/d3477946708b6bc5ac711c146c035ab67ed7aa1e.png)
![\[F(x) = \frac{1}{(1 - x)^2} \cdot \frac{1}{1 - \frac{x}{(1 - x)^2}} \]](http://latex.artofproblemsolving.com/d/a/7/da7ded8d3aab234743d1dee319bc3cb5d722cf6f.png)
![\[F(x) = \frac{1}{(1 - x)^2 -x} = \frac{1}{x^2 - 3x + 1} \]](http://latex.artofproblemsolving.com/9/f/9/9f942c864a93f4f803134bdc5759ae74ff065fad.png)
and 
; these are the roots of the quadratic in the denominator of . Then can be written as![\[F(x) = \frac{1}{\sqrt{5}} \left(\frac{1}{x - \alpha} - \frac{1}{x - \beta}\right)\]](http://latex.artofproblemsolving.com/9/e/b/9eb4d684d23dce1c6288e01620e2edf6dbb807ac.png)
![\[F(x) = \sum_{n \geq 0} \frac{1}{x\sqrt{5}} \left(\frac{1}{1 - \frac{\alpha}{x}} - \frac{1}{1 - \frac{\beta}{x}}\right) x^n\]](http://latex.artofproblemsolving.com/0/7/a/07ab5c3952716a7dd40f46f554a216f3d60c5725.png)
with :![\[F(x) = \sum_{n \geq 0} \frac{1}{x\sqrt{5}} \left(\frac{1}{1 - x \alpha} - \frac{1}{1 - x \beta}\right) x^n\]](http://latex.artofproblemsolving.com/c/9/c/c9cdf6fa3cbf4b0b998faa45ef9a0d8fe9eea6c0.png)
![\[F(x) = \sum_{n \geq 0} \frac{1}{\sqrt{5}} \left( \alpha^{n + 1} + \beta^{n + 1} \right) x^n\]](http://latex.artofproblemsolving.com/5/8/4/584a953a5cb09fcc2c7506925518c9cb51fb31d6.png)
![\[F(x) = \sum_{n \geq 0} \frac{1}{\sqrt{5}} \left( \left(\left(\frac{1 + \sqrt{5}}{2}\right)^2\right)^{n + 1} + \left(\left(\frac{1 - \sqrt{5}}{2}\right)^2\right)^{n + 1} \right) x^n\]](http://latex.artofproblemsolving.com/b/d/c/bdccf0ab67073202d5c8953735810393788190b3.png)
![\[F(x) = \sum_{n \geq 0} \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^{2n + 2} + \left(\frac{1 - \sqrt{5}}{2}\right)^{2n + 2} \right) x^n\]](http://latex.artofproblemsolving.com/b/1/f/b1fa42910348346a2c4be36678bd3545274e74ee.png)
![\[F(x) = \sum_{n \geq 0} F_{2n + 2} x^n\]](http://latex.artofproblemsolving.com/2/e/a/2eaec20ab925157b9eb80d1ad5cde1db2f11991b.png)
, as desired.
2. 
3. 
Bracket 2
2. 
3. 
Bracket 3![$$\int_0^{1}\frac{dx}{1-\sqrt[3]{1-\sqrt{x}}}$$](http://latex.artofproblemsolving.com/d/5/e/d5e8db00985944b2eca341e37a94e34661cb5c86.png)
2. 
3. 
Bracket 4
2. 
3. 
Bracket 5
2. 
3. 
Bracket 6
2. 
3. 
Bracket 7
2. 
3. 
Bracket 8
2. 
3. 
![$$\int_0^{2\pi}\sqrt[4]{\cos^4(x)-\cos(2x)}dx$$](http://latex.artofproblemsolving.com/7/e/e/7eebb4a488fec702e0130a253ef87f0f6dfedb2d.png)
2. ![$$\int_0^1 \frac{x^5}{\sqrt[3]{1-x^3}}dx$$](http://latex.artofproblemsolving.com/6/0/5/605bb9d81d0ccff54a276c9f7bf1c1726c136398.png)
3. 
Bracket 2
2. 
3. 
Bracket 3
2. ![$$\int_0^1 \frac{dx}{(\sqrt{x}+\sqrt[3]{x})^2}$$](http://latex.artofproblemsolving.com/6/9/8/69869c0ed754c0dfacf412ac6411742ffa164a6d.png)
3. 
Bracket 4
2. 
3. 
2. 
3. 
Bracket 2
2. 
3. 
2. 
3. 
2. 
3. 
4. 
5. 
and 
.
,
is the number of admissible pairs. This function can also be expressed as
![\[\sum_{a\ge 0}\sum_{b\ge 0}\binom{n-b}a\binom{n-a}b=\sum_{a\ge 0}\sum_{b\ge 0}\binom{n-b}{n-a-b}\binom{n-a}{n-a-b}=\sum_{k\ge 0}\sum_{a+b=k}\binom{n-b}{n-k}\binom{n-a}{n-k}.\]](http://latex.artofproblemsolving.com/9/c/f/9cf2399fd9b8b54fa4789aeeaec18329b0df1e8a.png)
Now we claim ![\[\sum_{a+b=k}\binom am\binom bn=\binom{k+1}{m+n+1}.\]](http://latex.artofproblemsolving.com/2/c/8/2c82c78c07367c516bb11d7103598c374642f8a1.png)
This follows from ![\[\sum_{k\ge 0}\sum_{a+b=k}\binom am\binom bnx^k=\left(\sum_{a\ge 0}\binom amx^a\right)\left(\sum_{b\ge 0}\binom bnx^b\right)=\frac{x^m}{(1-x)^{m+1}}\cdot\frac{x^n}{(1-x)^{n+1}}=\frac{x^{m+n}}{(1-x)^{m+n+2}}=\sum_{c\ge 0}\binom{c+1}{m+n+1}x^c.\]](http://latex.artofproblemsolving.com/d/b/1/db1be8017865c4042b40acc576329778fa99e6d1.png)
Thus we want ![\[\sum_{k\ge 0}\binom{2n-k+1}{2n-2k+1}=\sum_{k\ge 0}\binom{2n-k+1}k.\]](http://latex.artofproblemsolving.com/7/c/c/7cc7466ff7a5f6918d756e6af5dd75b39ea55cc2.png)
Now we claim ![\[\sum_{k\ge 0}\binom{a-k}k=F_{a+1}.\]](http://latex.artofproblemsolving.com/b/1/f/b1ff51ac1dcc4bfc512423a7f36dfe2304b76058.png)
This is because ![\[\sum_{a\ge 0}\sum_{k\ge 0}\binom{a-k}kx^a=\sum_{k\ge 0}\sum_{a\ge 0}\binom{a-k}kx^a=\sum_{k\ge 0}\frac{x^{2k}}{(1-x)^{k+1}}=\frac1{1-x}\left(\frac1{1-\frac{x^2}{1-x}}\right)=\frac1{1-x-x^2}=\sum_{a\ge 0}F_{a+1}x^a.\]](http://latex.artofproblemsolving.com/a/6/f/a6ff036eb071ae126452827e9fbbd9ed47db6a08.png)
Thus the answer is 
then 
and 
Thus, it follows that the number of admissible pairs is 
We wish to separate 
such that 
We can let 
both of the binomial coefficients will have a value of 
It follows that our expression becomes 
so if we let 
be the number of admissible pairs of subsets from the set 
then we get
Partially-decomposing this yields
where 
so it follows that 
Manipulating this using Binet's Formula (motivated by the fact that 
and 
)
