The number of edges in the $k$-dimensional cube $Q_k$ can be found by the recurrence relation: $e(Q_1)=1$; $e(Q_n)=2e(Q_{n-1})+2^{n-1}$ for $n\ge 2$

Question

We use the generating function technique to solve this recurrence relation and determine the number of edges in the $k$-dimensional cube. When I solve this, I get $2^n$ as my coefficient of $x^n$, which I would assume is my answer for the number of edges here?

Answer 1

Maybe it is quicker by double counting: every vertex has $n$ neighbours (meaning $n$ edges adjacent to it), but each vertex gets counted twice in such a way. Put differently

$2|E| = n 2^{n}$

For $n= 3$, we get the desired 12 edges, see the comment of Henry.

But the recurrence relation works too. Develop once or twice:

$e(Q_n) = 2 e(Q_{n-1}) + 2^{n-1} = 4 e(Q_{n-2}) + 2\cdot 2^{n-1} = \ldots = 2^{n-1}e(Q_1) + (n-1)2^{n-1} = n 2^{n-1}$

Answer 2

Let $a_n = e(Q_n)$. Your recurrence is $a_n = 2a_{n-1} + 2^{n-1}$ for $n \ge 2$, with initial condition $a_1=1$. Let $A(z) = \sum_{n \ge 1} a_n z^n$ be the generating function. Then $$\sum_{n \ge 2} a_n z^n = 2 \sum_{n \ge 2} a_{n-1} z^n + \sum_{n \ge 2} 2^{n-1} z^n, $$ so $$A(z) - z = 2z A(z) + \frac{2z^2}{1-2z}.$$ Solving for $A(z)$ yields \begin{align} A(z) &= \frac{z}{(1-2z)^2} = -\frac{1/2}{1-2z} + \frac{1/2}{(1-2z)^2} \\ &= -\frac{1}{2}\sum_{n \ge 0} (2z)^n + \frac{1}{2}\sum_{n \ge 0} \binom{n+1}{1}(2z)^n \\ &= \sum_{n \ge 1} n 2^{n-1} z^n, \end{align} which immediately implies that $a_n=n 2^{n-1}$ for $n \ge 1$.

Answer 3

You do not seem to have stated the generating function. One possible approach is

• $a_n = 2a_{n-1} + 2^{n-1}$
• so $a_n - 2a_{n-1} - 2^{n-1}=0$ and $2a_{n-1} - 4a_{n-2} - 2^{n-1}=0$
• and with subtraction $a_n - 4a_{n-1} + 4a_{n-2}=0$

giving a generating function with denominator $1-4x+4x^2 = (1-2x)^2$.

When $n=0$ we have $0$ edges, when $n=1$ we have $1$ edge (a line segment).

So the generating function is $$\sum a_nx^n=\dfrac{x}{(1-2x)^2}= x+4x^2+12x^3+32x^4+80x^5+\cdots$$

• If the generating function had been $\frac{1}{(1-x)^2}$ the solution would have been $a_n=n+1$
• If the generating function had been $\frac{1}{(1-2x)^2}$, replacing $x$ by $2x$ and so $x^n$ by $(2x)^n$, the solution would have been $a_n=(n+1)2^{n}$
• But the generating function is $\frac{x}{(1-2x)^2}$, making $a_{n+1}=(n+1)2^{n}$, so the solution is $$a_n=n2^{n-1}$$