Intereting Posts

Solutions of $\prod_{i=1}^n x_i = c$ mod p
Christoffel symbols and fundamental forms
Can the limit $\lim_{h \to 0}\frac{f(x + h) – 2f(x) + f(x – h)}{h^2}$ exist if $f'(x)$ does not exist at $x$?
Proof of fundamental theorem of integral calculus
Graph of a continuous real valued map is a nowhere dense set
Integral domain with a finitely generated non-zero injective module is a field
If coefficients of the Quadratic Equation are in AP find $\alpha+\beta +\alpha\beta$.
What seems to be the minors of the Adjugate matrix $\text{adj}(A)$ of a square matrix $A$?
Show that the standard integral: $\int_{0}^{\infty} x^4\mathrm{e}^{-\alpha x^2}\mathrm dx =\frac{3}{8}{\left(\frac{\pi}{\alpha^5}\right)}^\frac{1}{2}$
Let $A\subseteq\Bbb R$ with $\lambda^*(A)>0$. Show that there exists a nonmeasurable $B\subseteq\Bbb R$ s.t. $B\subseteq A$
Why do we need the partial derivative $\frac {\partial F}{\partial t}$ in the definition of an envelope?
Formula for the $1\cdot 2 + 2\cdot 3 + 3\cdot 4+\ldots + n\cdot (n+1)$ sum
Finding multivariable limits for the function $\frac{3x^2y}{x^2+y^2}$
Find $n$, where its factorial is a product of factorials
Heuristics for topological sort

If you toss a coin $n$ times, there are $2^n$ possible sequences of heads and tails. Let $E_n$ be the set of sequences which do NOT contain two consecutive heads and $e_n$, the number of sequences in $E_n$.

Thus $E_3$ $=$ $\{$ $TTT$, $TTH$, $THT$, $HTT$, $HTH$ $\}$ and $e_3$ $=$ $3$.

How many elements of $E_n$ have $T$ as the first toss?

- What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?
- Prove that $\sum\limits_{k=0}^r\binom{n+k}k=\binom{n+r+1}r$ using combinatoric arguments.
- How many lists of 100 numbers (1 to 10 only) add to 700?
- Find all permutations in increasing order
- arrangement of $n$ oranges and $n$ apples around a circle
- Number of ways to write set $S$ as union of $l$ unique $k$-subsets

Please can anyone help me out here?

- Combinatorics: How to find the number of sets of numbers in increasing order?
- Is there a “counting groups/committees” proof for the identity $\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$?
- Can $e_n$ always be written as a linear combination of $n$-th powers of linear polynomials?
- A set of integers whose elements all divide $2015^{200}$ but do not divide each other
- N.Alon, J.Spencer Probabilistic methods problem ch. $4$ problem $5$
- Flipping heads 10 times in a row
- In how many ways can five letters be posted in 4 boxes?
- Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular
- Counting ways to partition a set into fixed number of subsets
- No. of possible solutions of given equation

Well, let’s say we have some sequence $TXXXX…$ in $E_n$. Now, take the $T$ off so that we just have $XXXX…$. Since $TXXXX…$ must have no consecutive heads, it must also have no consecutive heads without the $T$. Therefore, $XXXX…$ is an element of $E_{n-1}$. Furthermore, if we have some sequence $YYYY…$ in $E_{n-1}$, then by adding a $T$ to it, there’s no way we’re adding any consecutive heads to the sequence since $T$ does not have any heads to it, so $TYYYY…$ is in $E_n$. Thus, every sequence that starts with $T$ in $E_n$ can be mapped to a unique sequence in $E_{n-1}$ and vice versa, so the number of sequences that start with $T$ in $E_n$ is $\lvert E_{n-1}\rvert$.

Well, now we need to figure out what $E_{n-1}$ is. To do this, let’s look at the question how many sequences in $E_n$ start with $H$. Let’s say we have some sequence $HXXXX…$ in $E_n$. Then, if the second letter is $H$, then we have consecutive heads, which can’t be since sequences in $E_n$ don’t have consecutive heads. Thus, the second letter is a $T$, so the sequence is $HTXXX…$. Now, take the $HT$ off and we’re left with $XXX…$. This sequence does not have any consecutive heads since the original sequence did not have any consecutive heads, so $XXX…$ is in $E_{n-2}$. Furthermore, let’s take a sequence $YYY…$ in $E_{n-2}$. Now, let’s add $HT$ to it. There’s no way $HTYYY…$ has any consecutive heads because even if the first letter of $YYY…$ is an $H$, then we just get $HTH$ which has no consecutive heads. Thus, $HTYYY…$ is an element of $E_n$. Thus, every sequence that starts with $H$ in $E_n$ can be mapped to a unique sequence in $E_{n-2}$ and vice versa, so the number of sequences that start with $H$ in $E_n$ is $\lvert E_{n-2}\rvert$.

Now, any sequence in $E_n$ either starts with $H$ or $T$. That means any sequence in $E_n$ is either in the group of $\lvert E_{n-1}\rvert$ sequences beginning with $T$ or in the group of $\lvert E_{n-2}\rvert$ sequences beginning with $H$. Since $E_n$ is made up solely of these two groups, the total number of sequences must be $\lvert E_{n-1}\rvert+\lvert E_{n-2}\rvert$, giving us:

$$\lvert E_n \rvert=\lvert E_{n-1}\rvert+\lvert E_{n-2}\rvert$$

This is the Fibonacci sequence recurrence. Now, we need to find the initial elements, which is $n=1$ and $n=2$. Both $T$ and $H$ are in $E_1$, so $\lvert E_1\rvert=2$ while $TH$, $TT$, and $HT$ are in $E_2$, so $\lvert E_2\rvert=3$. Thus, this is the Fibonacci sequence shifted over 2 elements (since $F_3=2$ and $F_4=3$), so we find that:

$$\lvert E_n\rvert=F_{n+2}$$

Finally, we wanted the number of sequences that start with $T$, which we found to be $\lvert E_{n-1}\rvert$, which is $F_{n+1}$.

This type of combinatorics problem is best approached by trying to build up some recurrence relations among several related values, then solving that recurrence relation. (This type of problem shows up on here frequently – for example, see this problem and also this one)

So let’s define:

$e_n$ as you have it – the number of sequences of $n$ coin tosses without consecutive heads

$f_n$ the number of sequences of $n$ coin tosses without consecutive heads that do not begin with $H$

Similarly to what you defined in the problem statement, let $F_n$ be the actual sequences of $n$ coin tosses without consecutive heads that do not begin with $H$. Note that $F_n \subset E_n$.

Note that $f_n$ is what we want, but I defined it the way I did so that we can have $e_0 = f_0 = 1$.

Now, the relation between these series is straightforward: a sequence in $E_n$ is either $T$ followed by one of the elements of $E_{n-1}$, or $H$ followed by one of the elements of $F_{n-1}$.

So:

\begin{align}

e_0 &= 1 \\

f_0 &= 1 \\

e_n &= e_{n-1} + f_{n-1} \\

f_n &= e_{n-1}

\end{align}

Therefore, if we look at a few values of $e_n$ we get: (starting with $e_0$)

$$

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

$$

So in fact the sequence $e_n$ is the Fibonacci sequence, and $f_n$ – what we wished to find – is just $e_{n-1}$. (Depending on how your book defines where the Fibonacci sequence starts, $f_n$ is exactly the Fibonacci sequence and $e_n$ is the Fibonacci sequence shifted by one)

Note that this implies that as $n \to \infty$, the proportion of $E_n$ that begin with $T$ approaches $(\sqrt{5} – 1)/2 \approx 0.618$

- Proof of the duality of the dominance order on partitions
- Green's Theorem
- Calculating in closed form $\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{m^4(m^2+n^2)}$
- Why is there antagonism towards extended real numbers?
- Is there a quick way to find the remainder when this determinant is divided by $5$?
- Non-circular proof of $\lim_{\theta \to 0}\frac{\sin\theta}{\theta} = 1$
- Measurability of the composition of a measurable map with a surjective map satisfying an expansion condition
- Unbiased estimator of a uniform distribution
- Integral of differential form and integral of measure
- Where do the first two numbers of Fibonacci Sequence come from?
- Why can't Fubini's/Tonelli's theorem for non-negative functions extend to general functions?
- Why there isn't any solution in positive integers for $z^3 = 3(x^3 +y^3+2xyz)$?
- Prove that $G$ is abelian iff $\varphi(g) = g^2$ is a homomorphism
- Does the isomorphism $k\otimes_k k\cong k$ hold?
- Prove that $\sum\limits_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= \sum\limits_{n=0}^{\infty}\frac{1}{2^{n}}$