Intereting Posts

If a holomorphic function $f$ has modulus $1$ on the unit circle, why does $f(z_0)=0$ for some $z_0$ in the disk?
What does it mean to integrate with respect to the distribution function?
How to reverse digits of an integer mathematically?
Sets of Constant Irrationality Measure
Prove: If a sequence converges, then every subsequence converges to the same limit.
Characterization of real functions which have limit at each point
where to find the tables of irreducible character of the sporadic simple groups and their automorphism groups?
Unbiased estimator of the variance with known population size
Find an $n\times n$ integer matrix with determinant 1 and $n$ distinct eigenvalues
Recurrence relation (linear, second-order, constant coefficients)
Upper bound on cardinality of a field
find all self-complementary graphs on five vertices
Numbers that are the sum of the squares of their prime factors
Inequality Of Four Variables
Finite Field Extensions and the Sum of the Elements in Proper Subextensions (Follow-Up Question)

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?

- A combinatorial task I just can't solve
- Finding total number of multi-sets
- Exploring Properties of Pascal's Triangle $\pmod 2$
- What is the Probability that a Knight stays on chessboard after N hops?
- Given $n$ distinct elements, how many Young Tableaux can you make?
- Finding the probability that red ball is among the $10$ balls

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!

- Double sum and zeta function
- Prove that $\int_0^{\infty} \frac{t^n} {1+e^t}dt=(1-2^{-n})n!\zeta (n+1)$
- Theorem 3.55 Rudin (rearrangement and convergence)
- Does $\sum\frac{\sin n}{n}$ converge?
- Convergence of the series $\sum_ {n\geq1} \frac {(f(n) +P(n)) \pmod {Q(n)}} {D(n)}$
- Conditionally combining vanilla and chocolate ice cream scoops
- Combinatorics identity question
- Convergence of $\frac{a_n}{n}$ where $a_0=1$ and $a_n=a_{\frac{n}{2}}+a_{\frac{n}{3}}+a_{\frac{n}{6}}$
- How to prove that this series is a metric: $d(x,y):=\sum_{i=0}^\infty \frac{|x_i -y_i|}{2^i (1+|x_i-y_i|)}$
- A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$

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}

$$

- Drawing a thickened Möbius strip in Mathematica
- Can there be generalization of Monty Hall Problem?
- Does $\int_{0}^{\infty}\frac{dx}{1+(x\sin5x)^2}$ converge?
- Exponential Generating Functions For Derangements
- Number of roots of a polynomial over a finite field
- If $n>m$, then the number of $m$-cycles in $S_n$ is given by $\frac{n(n-1)(n-2)\cdots(n-m+1)}{m}$.
- Show that a Cauchy sequence has a fast-Cauchy subsequence
- book with lot of examples on abstract algebra and topology
- How can we integrate $\int_{0}^{\frac{\pi }{2}}\left(\frac{\sin nx}{\sin x}\right)^{4}\,dx$?
- Composition of a harmonic function with a holomorphic function
- Very confused about a limit.
- Double Negation is sequent calculus systems LK and LJ
- Finite Element Method for a Two-Point Problem
- The kernel of the transpose of the differentiation operator – Solution check
- Why do we find Gödel's Incompleteness Theorem surprising?