Intereting Posts

Monotone Convergence Theorem for non-negative decreasing sequence of measurable functions
Help with using the Runge-Kutta 4th order method on a system of 2 first order ODE's.
Open Set and Measure Theory
References on filter quantifiers
Is this field extension finite?
Is it faster to count to the infinite going one by one or two by two?
How to project the surface of a hypersphere into the full volume of a sphere?
Solve an integral $\int\left(\frac{x^{1/3}-1}{x}\right)^{5/3}dx$
Proving $f(C) \setminus f(D) \subseteq f(C \setminus D)$ and disproving equality
In how many ways can we arrange 4 letters of the word “ENGINE”?
surface Areas using cylindrical shells
Calculate average angle after crossing 360 degrees
Find the coordinates of a point on a circle
What is the difference between “family” and “set”?
how to calculate area of 3D triangle?

Possible Duplicate:

How many $N$ digits binary numbers can be formed where $0$ is not repeated

I am really embarrassed to ask this as it seems like a textbook question.But it is not, and I am at a complete loss how to get a grip on it.It is mentioned in the first lecture of a 24 lecture series on Discrete Mathematics by the popular Mr.Arthur Benjamin(Discrete Mathematics-The Great Courses),which I am following.He only fleetingly mentions that we use combinatorics to solve this and starting with n=1 (1 bit number), the answer follows the Fibonacci pattern 2,3,5,8……So please answer this for me lest I get discouraged from the start of the subject itself.

i)If we are asked to find the number of n-length binary numbers with no consecutive zeroes,then how do we go about it?I have a fair idea about combinatorics,binary coefficients,permutations, yet I just can’t figure how to start.So what is the logic we use?

- Formula for binomial coefficients
- Why is it important to study combinatorics?
- How many bracelets can be formed?
- $\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Combinatorial proof
- Maximum edges in a square free graph
- Using generating functions to find a formula for the Tower of Hanoi numbers

ii)Why does it follow a Fibonacci pattern for n,n+1,n+2 and so on?This further bewilders me.Why on earth is a Fibonacci pattern generated?There must be an explanation…

Your clear and easy-to-understand answers will go a long way in motivating me further into the subject.Thanks!

- Limit of the geometric sequence
- Compute $ \sum\limits_{m=1}^{\infty} \sum\limits_{n=1}^{\infty} \sum\limits_{p=1}^{\infty}\frac{(-1)^{m+n+p}}{m+n+p}$
- If there are 200 students in the library, how many ways are there for them to be split among the floors of the library if there are 6 floors?
- Number of Pairs of Subsets
- Catalan numbers - number of ways to stack coins
- How to derive an explicit formula for $\sum \frac{e^{i n \theta}}{n}?$
- How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$
- A surprising inequality about a $\limsup$ for any sequence of positive numbers
- How to prove $\sum_{n=0}^{\infty} \frac {(2n+1)!} {2^{3n} \; (n!)^2} = 2\sqrt{2} \;$?
- $\{a_n\}$ sequence $a_1=\sqrt{6}$ for $n \geq 1$ and $a_{n+1}=\sqrt{6+a_n}$ show it that convergence and also find $\lim_{x \to \infty} \{a_n\}$

Consider the length $n$ binary strings with no repeated zeros (BSWNRZ).

BSWNRZ must end in a $0$ or a $1$. The number of BSWNRZ of length $n$ that end in a $0$ is equal to the number of BSWNRZ of length $n-2$ (with $10$ appended). The number of BSWNRZ of length $n$ that end in a $1$ is equal to the number of BSWNRZ of length $n-1$ (with $1$ appended).

That is, any length $n$ BSWNRZ falls into one of the following two cases

$$

\overbrace{?????????????????}^{\text{any length }n-2\text{ BSWNRZ}}\color{#00A000}{1}\color{#C00000}{0}\\

\underbrace{??????????????????}_{\text{any length }n-1\text{ BSWNRZ}}\color{#C00000}{1}

$$

Therefore, the number of BSWNRZ of length $n$ is equal to the number of BSWNRZ of length $n-1$ plus the number of BSWNRZ of length $n-2$. Thus, the Fibonacci pattern.

$$

F_n=F_{n-1}+F_{n-2}

$$

- Number of subgroups of prime order
- Reflections on math education
- Limit of $n/\ln(n)$ without L'Hôpital's rule
- Is every subset of $\mathbb{Z^+}$ countable?
- $f:\mathbb{S}^1\rightarrow\mathbb{S}^1$ odd $\Rightarrow$ $\mathrm{deg}(f)$ odd (Borsuk-Ulam theorem)
- Meaning of the identity $\det(A+B)+\text{tr}(AB) = \det(A)+\det(B) + \text{tr}(A)\text{tr}(B)$ (in dimension $2$)
- Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF
- Every open subset $O$ of $\Bbb R^d,d \geq 1$, can be written as a countable union of almost disjoint closed cubes.
- A question regarding power series expansion of an entire function
- Cartesian products of families in Halmos' book.
- Find an orthonormal basis of a plane
- How do you integrate a Bessel function? I don't want to memorize answers or use a computer, is this possible?
- Find all functions f such that $f(f(x))=f(x)+x$
- Reason for Continuous Spectrum of Laplacian
- Sufficient conditions for exchangeability of random variables