Proof $C_h = \binom{2^h-2}{2^{h-1}-1} C_{h-1}^2$ can be written non-recursively as $C_h = \frac{(2^h-1)!}{\prod_{k=1}^h (2^k-1)^{2^{h-k}}}. $

Question

I have to proof A056972 by induction. It says that the recurrence relation.

$$ C_h = \binom{2^h-2 }{2^{h-1}-1} C_{h-1}^2. $$

Can be expressed as

$$ C_h = \frac{(2^h-1)!}{\prod_{k=1}^h (2^k-1)^{2^{h-k}}}. $$

When I tried proving it my steps were the following

$$ C_{h+1} = \binom{2^{h+1}-2}{2^{h}-1}\cdot\left(\frac{(2^h-1)!}{\prod_{k=1}^h (2^k-1)^{2^{h-k}}}\right)^2. $$ Since $2^{h+1}-2-(2^h-1)=2^h-1$ we get $$ C_{h+1}=\frac{(2^{h+1}-2)!}{\prod_{k=1}^h (2^k-1)^{2^{h-k+1}}} $$ However from this expression onwards I'm stuck and it seems to me that the nominators should get smaller while the denominator gets bigger inorder to get the result by induction, which does not work.

Answer 1

You are basically there... but you need one more step. Your last statement is correct as it stands.

$$C_{h+1}=\frac{(2^{h+1}-2)!}{\prod_{k=1}^h{(2^k-1)^{2^{h+1-k}}}}$$

Now, multiply the top and bottom by $(2^{h+1}-1)$.

$$C_{h+1}=\frac{(2^{h+1}-2)!}{\prod_{k=1}^h{(2^k-1)^{2^{h+1-k}}}}\cdot \frac{(2^{h+1}-1)}{(2^{h+1}-1)}=\frac{(2^{h+1}-1)!}{\prod_{k=1}^{h+1}{(2^k-1)^{2^{h+1-k}}}}$$

You can see by expanding out the denominator that it works as

$$\prod_{k=1}^{h+1}{(2^k-1)^{2^{h+1-k}}}=(2^1-1)^{2^h}(2^2-1)^{2^{h-1}}...(2^h-1)^{2^1}(2^{h+1}-1)^{2^0}$$