AoPS Academy
increasing with
? increasing with
?
such that 
for all real numbers 
is the greatest integer less than or equal to 
)
be a function, two times derivable on 
for which there exist 
such that![\[ \frac { f(b)-f(a) }{b-a} \neq f'(c) ,\]](http://latex.artofproblemsolving.com/a/3/1/a31861ef909a6e17ed8b495b9b9b16d887ba573f.png)
for all 
.
.
be positive real numbers .
, whether or not the polynomial 
irreducible over 
?
such that the equation in the unknown 
:
admits 
roots: 
s.t. 
.
does there exist an 
matrix 
whose entries are all in 
, such that 
is the matrix of all ones?
, 
is biased so that, when tossed, it has probability 
of falling heads. If the coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function .
![$ = \frac{1}{2} \left [ \left ( \frac{1}{2k+1} + \frac{2k}{2k+1} \right )^{n} + (-1)^{n+1} \left ( \frac{1}{2k+1} - \frac{2k}{2k+1} \right )^{n} \right ]$](http://latex.artofproblemsolving.com/5/5/7/557de3c48c6411218705b4a13e01e5ed3750b95e.png)
denote the probability that given 
coins we have an odd number coming up heads, and 
similarly except for even.
and 
.
and 
and 
and 
, hence the answer is 
.
coins 
, and the probability that 
when flipped will land heads is ![$\Pr[C_k = H] = 1/(2k+1)$](http://latex.artofproblemsolving.com/6/6/f/66f04110a227c213a6ca88771c52a3a7f4509ee1.png)
for each 
. Therefore, you cannot regard distinct 
-subsets of the as having equivalent probabilities of showing heads.
.
, 
.
, the probability that the number of heads is odd among the 
tosses is 
. Then, correspondingly, the probability that the number of heads is even is 
.
. Consider the -th toss. If the number of heads is odd for the first tosses, we need the -th toss be a tail; otherwise, we need it to be a head. So the probability that after -th toss the total number of heads is odd is ![\[\dfrac{k-1}{2k-1}\cdot(1 - \dfrac{1}{2k + 1}) + \dfrac{k}{2k-1}\cdot\dfrac{1}{2k+ 1} = \dfrac{2k^2 - k}{(2k-1)(2k+1)} = \dfrac{k}{2k+1}\]](http://latex.artofproblemsolving.com/b/3/8/b3860ed78d392db59f1b0b2ae78139584af9fa06.png)
This completed the inductive proof.
) is indeed equal to the product of probabilities that those respective coins are even/odd. This statement wouldn't be too difficult to prove by induction though.
heads is the coefficient of 
in 
denote the probability of tossing an odd number of heads the first tosses. Then, 
with 
. Computing the first few values of , they are 
, 
, 
, and 
. We now try to prove that 
by induction.: we have 
which is true., we show that the statement holds for 
:
we have .
be the probability that the number of heads is odd for coins and similarly define 
for an odd number of heads. Then, by considering 
we have the recurrence 
and 
. Note that for every coefficient of a term 
in the expansion of this function, this represents the number of ways to flip the coins so that the number of heads displayed is equal to . Additionally, note that by setting 
, we have that the exponents of all terms are positive, while setting 
makes only the coefficients of the terms with an even exponent of 
positive, while the coefficients of the terms with an odd exponent of are negative. Thus, our desired probability becomes
where we divide by 
to account for each of the coefficients with an odd exponent of being added twice. Note that
Thus, our expression becomes
![$\mathcal{E}_n := \mathbb{P}[\text{even number of heads for a toss of n coins}]$](http://latex.artofproblemsolving.com/1/5/b/15b9f3ebb2e6c8aebfa71d8257badffa771c2bc8.png)
![$\mathcal{O}_n := \mathbb{P}[\text{odd number of heads for a toss of n coins}]$](http://latex.artofproblemsolving.com/b/8/4/b844b81771c136e4b155b8cc23f3a62497482ce3.png)
.
Subtracting above two equations,
Interating we have, 
Here 
and 
.![$\mathcal{O}_n=\frac{1}{2}[(\mathcal{E}_n+\mathcal{O}_n)-(\mathcal{E}_n-\mathcal{O}_n)]=\frac{1}{2}\left(1-\frac{1}{2n+1}\right) = \boxed{\frac{n}{2n+1}}$](http://latex.artofproblemsolving.com/6/f/4/6f4d7e8e18f7930eadd776a6b2426d46a3d73f2e.png)
The coefficient of gives the probability of achieving heads. Thus the desired quantity is the sum of the odd degree coefficients, which is given by 
. We can easily see that 
. On the other hand, 
, which telescopes to . Thus the answer is 
denote the required probability.
, we get 
.
![\[
\mathbb{P}(\text{H}) = \frac{1}{2k+1}, \quad \mathbb{P}(\text{T}) = \frac{2k}{2k+1}
\]](http://latex.artofproblemsolving.com/c/9/b/c9bd64a81fcb5a54313af26f7027e8cb65304d3f.png)
![\[
\left( \frac{1}{2k+1} + \frac{2k}{2k+1} \right)^n \quad \text{and} \quad \left( \frac{2k}{2k+1} - \frac{1}{2k+1} \right)^n
\]](http://latex.artofproblemsolving.com/b/b/4/bb46d190139d4c60f2ddfd8322bac1d974879734.png)
![\[
F_1^k = \left( \frac{1}{2k+1} + \frac{2k}{2k+1} \right), \quad
F_2^k = \left( \frac{2k}{2k+1} - \frac{1}{2k+1} \right)
\]](http://latex.artofproblemsolving.com/7/6/0/76003c79d9d983c9a5c2629e0b6d0a59909e8703.png)
![\[
\frac{\prod_{k=1}^{n}F_1^k - \prod_{k=1}^{n}F_2^k}{2}
\]](http://latex.artofproblemsolving.com/0/a/e/0ae7abe73aa7c8d0a54ccbee1adffb34441990f0.png)
![\[
\prod_{k=1}^{n} F_1^k = 1
\]](http://latex.artofproblemsolving.com/e/8/a/e8ab200d45e3126c1614250482c1d5282e664dbe.png)
![\[
\prod_{k=1}^{n} F_2^k = \prod_{k=1}^{n} \frac{2k - 1}{2k + 1} = \frac{1}{3} \cdot \frac{3}{5} \cdot \frac{5}{7} \cdots \frac{2n - 1}{2n + 1}
= \frac{1}{2n + 1}
\]](http://latex.artofproblemsolving.com/c/4/5/c450fdab6ad6728fbe012d349202752d6761ca5b.png)
![\[
\frac{1 - \frac{1}{2n + 1}}{2} = \frac{n}{2n + 1}
\]](http://latex.artofproblemsolving.com/d/f/8/df8fb1c18e9f612960dbceb2a2a18f4151d61e52.png)
Latexed by Leviee....solved by me....thanks Leviee
![\[ \int_{-1}^{1} e^x \sin \sqrt{1-x^2} \, \mathrm dx .\]](http://latex.artofproblemsolving.com/0/f/0/0f01e4820da5328db8b1b55947de2148cbdd3e83.png)
![$\underset{n\to \infty }{\mathop{\lim }}\,\sqrt[n]{lcm(1,2,3,...,n)}=e$](http://latex.artofproblemsolving.com/a/1/3/a139e5cb990f3386de109c701f8edc71b4054712.png)
and 
be the probabilities that the number of heads is even or odd, respectively. Then 
and![\[E-O=\left(\frac{2}{3}-\frac{1}{3}\right)\cdot\left(\frac{4}{5}-\frac{1}{5}\right)\cdots\left(\frac{2n}{2n+1}-\frac{1}{2n+1}\right)=\frac{1}{3}\frac{3}{5}\cdots\frac{2n-1}{2n+1}=\frac{1}{2n+1},\]](http://latex.artofproblemsolving.com/0/1/9/01971cdafd04942b458e75522282031c4d3dd08b.png)
so 
.![\[E-O=\left(\frac{2}{3}-\frac{1}{3}\right)\cdot\left(\frac{4}{5}-\frac{1}{5}\right)\cdots\left(\frac{1}{2n+1}-\frac{1}{2n+1}\right)=\frac{1}{3}\frac{3}{5}\cdots\frac{2n-1}{2n+1}=\frac{1}{2n+1},\]](http://latex.artofproblemsolving.com/0/4/3/0438e4ad7df6378df442af9ad9585c6cb6035bb5.png)
so 
instead of 
![\[
O(n) = \mathbb{P}(\text{odd number of heads in } n \text{ tosses})
\]](http://latex.artofproblemsolving.com/4/c/4/4c415436aa6f27721ebf548d83dc4f1d9746955b.png)
![\[
E(n) = \mathbb{P}(\text{even number of heads in } n \text{ tosses})
\]](http://latex.artofproblemsolving.com/2/b/d/2bda81921e1a0a68f2c3f2a59aba9434cbceddc9.png)
![\[
O(n) + E(n) = 1
\]](http://latex.artofproblemsolving.com/b/8/8/b8825d581dd0efded9c6a5f7299cf182afafb1ca.png)
![\[
\text{Observe that:}
\]](http://latex.artofproblemsolving.com/e/0/3/e036292ed4e4ce7f008a1233fa4c921cb19e1e96.png)
![\[
O(n) = O(n-1) \cdot \mathbb{P}(\text{last toss is tails}) + E(n-1) \cdot \mathbb{P}(\text{last toss is heads})
\]](http://latex.artofproblemsolving.com/4/9/6/496f574ca067f23b5fc2c54209c3654f1cee9685.png)
![\[
\Longrightarrow O(n) = O(n-1) \cdot \frac{2n}{2n+1} + E(n-1) \cdot \frac{1}{2n+1}
\]](http://latex.artofproblemsolving.com/8/6/6/8665ee81a9f65806743fbd7b93aa580cf1ddfba6.png)
![\[
\Longrightarrow \boxed{O(n) = O(n-1) \cdot \frac{2n}{2n+1} + (1 - O(n-1)) \cdot \frac{1}{2n+1}}
\]](http://latex.artofproblemsolving.com/a/5/7/a57e1f7256a027eb73fe308385f8823fd3595121.png)