Recall the definition of the Fibonacci numbers:
Let $a=\frac{1+\sqrt{5}}{2}$ and $b=\frac{1-\sqrt{5}}{2}$.
Claim: $\displaystyle F_n = \frac{a^n-b^n}{a-b}$.
Let's first prove an easy (but non-obvious) lemma:
Lemma: $a^2 = a+1$ and $b^2 = b+1$.
$a^2 = (\frac{1+\sqrt{5}}{2})^2 = \frac{1+ 2\sqrt{5} + 5}{4} = \frac{6 + 2\sqrt{5}}{4} = \frac{3+ \sqrt{5}}{2} = 1 + \frac{1+\sqrt{5}}{2} = 1+a$.
$b^2 = (\frac{1-\sqrt{5}}{2})^2 = \frac{1 - 2\sqrt{5} + 5}{4} = \frac{6 - 2\sqrt{5}}{4} = \frac{3 - \sqrt{5}}{2} = 1 + \frac{1-\sqrt{5}}{2} = 1+b$.
The inductive proof:
Proof by induction on $n$.
Base cases:
At $n=0$, $F_n = 0$. Also $\frac{a^n-b^n}{a-b} = \frac{1-1}{a-b} = 0$.
At $n=1$, $F_n = 1$. Also $\frac{a^n-b^n}{a-b} = \frac{a-b}{a-b} = 1$.
Inductive Hypothesis: Suppose that $F_n = \frac{a^n-b^n}{a-b}$, for $n=0,\ldots,k-1$.
Rest of the inductive step:
$F_k = F_{k-1} + F_{k-2}$
By the inductive hypothesis, $F_{k-1} = \frac{a^{k-1}-b^{k-1}}{a-b}$ and $F_{k-2} = \frac{a^{k-2}-b^{k-2}}{a-b}$.
Substituting gives us
$F_k = \frac{a^{k-1}-b^{k-1}}{a-b} + \frac{a^{k-2}-b^{k-2}}{a-b}$
Simplifying:
$\begin{eqnarray*} F_k &=& \frac{a^{k-1}-b^{k-1}}{a-b} + \frac{a^{k-2}-b^{k-2}}{a-b} \\ &=& \frac{1}{a-b}(a^{k-1}-b^{k-1} + a^{k-2}-b^{k-2}) \\ &=& \frac{1}{a-b}(a^{k-2}(a+1) - b^{k-2}(b+1)) \end{eqnarray*}$
Recall from the lemma that $a^2 = a+1$ and $b^2 = b+1$. Substituting this gives us
$\begin{eqnarray*} F_k &=& \frac{1}{a-b}(a^{k-2}(a+1) - b^{k-2}(b+1)) \\ &=& \frac{1}{a-b}(a^{k-2}(a^2) - b^{k-2}(b^2)) \\ &=& \frac{1}{a-b}(a^k - b^k) \end{eqnarray*}$
So $F_k = \frac{a^k - b^k}{a-b}$, which is what we needed to show.
Obviously someone spent some time fiddling around with the Fibonacci numbers and similar equations, to come up with the concept for this closed form. But you can get some insight into the definitions of $a$ and $b$ by noticing that the lemma works in both directions.
Specifically, suppose you decide that you want to have $p^2 = p+1$ because that's going to make your inductive step work out. We can rewrite this constraint as $p^2 - p -1 = 0$. Applying the quadratic formula gives you $p = \frac{1 \pm \sqrt{1 + 4}}{2} = \frac{1 \pm \sqrt{5}}{2}$. So $p$ is equal to either $a$ or $b$ from the above proof.
The first hypercube $Q_0$ is a single node graph. \(Q_n\) is created
by taking two copies of \(Q{n-1}\) and joining corresponding nodes.
The number of nodes V(n) in the n-dimensional hypercube is \(2^n\). The number of edges can be defined recursively like this:
Putting different values into the recursive part of the definition:
Step 1: substitute the recursive part of the definition into itself, twice:
\( \begin{eqnarray*} E(n) &=& 2E(n-1) + 2^{n-1} \\ &=& 2(2E(n-2) + 2^{n-2}) + 2^{n-1} \\ &=& 2(2(2E(n-3) + 2^{n-3})+ 2^{n-2}) + 2^{n-1} \\ \end{eqnarray*} \)
Step 2: clean up the equation to make the pattern easier to see
\( \begin{eqnarray*} E(n) &=& 2(2(2E(n-3) + 2^{n-3})+ 2^{n-2}) + 2^{n-1} \\ &=& 2^3 E(n-3) + 2\cdot 2 \cdot 2^{n-3}+ 2\cdot 2^{n-2} + 2^{n-1} \\ &=& 2^3 E(n-3) + 2^{n-1}+ 2^{n-1} + 2^{n-1} \\ &=& 2^3 E(n-3) + 3 \cdot 2^{n-1} \end{eqnarray*} \)
Step 3: Guess the general pattern:
\( E(n) = 2^3 E(n-3) + 3 \cdot 2^{n-1} = \ldots = 2^k E(n-k) + k \cdot 2^{n-1} \)
Notice the term E(n-k).
Step 4: figure out what value of k will hit the base case of our definition, which is E(0) = 0. To do this, we set the input n-k equal to the input value in the base case. That gives us n-k = 0. So we will hit the base case when k=n.
Step 5: substitute k=n into our formula and simplify the result.
\( E(n) = 2^k E(n-k) + k \cdot 2^{n-1} = 2^n E(0) + n \cdot 2^{n-1} = 2^n \cdot 0 + n \cdot 2^{n-1} = n \cdot 2^{n-1} \)
Unrolling is not a proof and it's easy to make small errors doing unrolling. So we need to prove that our closed form is correct.
Claim: For every natural number n, \(E(n) = n2^{n-1} \).
Proof: by induction on n.Base case: at n=0, E(0) = 0. Also, \(n2^{n-1} = 0 \cdot 2^1 = 0\). So \(E(n) = n2^{n-1} \) at n=0.
Inductive hypothesis: Suppose that \(E(n) = n2^{n-1} \), for \(n=0,1,\ldots, k\).
Rest of inductive step:
The definition of E gives us \(E(k+1) = 2E(k) + 2^{k}\).
By the inductive hypothesis, we know that $E(k) = k2^{k-1}$
So \(E(k+1) = 2(k2^{k-1}) + 2^{k} = k2^{k} + 2^k = (k+1)2^k \)
So \(E(k+1) = (k+1)2^{k} \), which is what we needed to prove.
Claim: For any positive integer $n \ge 2$, if $G$ is a graph with $n$ nodes and more than $(n-1)(n-2)/2$ edges, then $G$ is connected.
Key technique: start with the big graph. Remove a node to create a smaller graph. Use the IH on the smaller graph.
Note: "more than" means >, not $\ge$.
Proof by induction on $n$, which is the number of nodes in the graph.
Base case: At $n=2$, we have $(n-1)(n-2)/2 = 0$. So the graph has two nodes and one edge. There's only one such graph and it's connected.
Inductive Hypothesis: If $G$ is a graph with $n$ nodes and more than $(n-1)(n-2)/2$ edges, then $G$ is connected, for $n=2, \ldots, k-1$.
Rest of the inductive step: Let $G$ be a graph with $k$ nodes and more than $(k-1)(k-2)/2$ edges. We want to show that $G$ must be connected.
Pick any node $x$ in $G$. Remove $x$ (and its edges) to produce a smaller graph $H$.
Case 1: $x$ is connected to all the other $k-1$ nodes in $G$. Then there is a path from any node to any other node, via $x$. So $G$ is connected.
Case 2: $x$ is connected to $k-2$ or fewer nodes.
$G$ has more than $(k-1)(k-2)/2$ edges. When we created $H$ by removing $x$, we removed $k-2$ or fewer edges. So $H$ must have more than $\frac{(k-1)(k-2)}{2} - (k-2)$ edges.
Notice that $\frac{(k-1)(k-2)}{2} - (k-2) = \frac{(k-1)(k-2)}{2} - \frac{2(k-2)}{2} = \frac{(k-3)(k-2)}{2}$
So $H$ has $k-1$ nodes and more than $(k-3)(k-2)/2$ edges. By the inductive hypothesis, $H$ must be connected.
In order to show that the larger graph $G$ is connected, we must show that our node $x$ must be connected to some node in $H$.
$H$ has $k-1$ nodes. The maximum of edges in a complete graph on $k-1$ nodes is $(k-1)(k-2)/2$. So that's the maximum number of nodes that $H$ could contain.
We assumed (way at the start) that $G$ has more than $(k-1)(k-2)/2$ edges. $H$ contains $(k-1)(k-2)/2$ or fewer edges. So $G$ must contain an edge that's not in $H$. That edge must connect $x$ to some node in $H$.
Since $H$ is connected, and $x$ is connected to a node in $H$, the full graph $G$ is connected, which is what we needed to prove.