I was looking through some old threads. $c(n,k)$ is, in fact, the number of vector subspaces of dimension $k$ in a vector space of dimension $n$ over $\mathbb F_2$ (the field with $2$ elements). Anyway, we can show, by induction, that the explicit formula for $c(n,k)$ is $\frac{u_n(2)}{u_k(2)\cdot u_{n-k}(2)}$, where $u_n(a)=(a^n-1)(a^{n-1}-1)\ldots(a-1)$. It's obvious from the formula that the conclusion holds.

Show that \[ c(n,k)=\frac{\prod_{l=1}^n (2^l-1)}{\prod_{l=1}^k (2^l-1)\prod_{l=1}^{n-k} (2^l-1)} \] by plugging it into the recurrence. This is a special case of the $q$-binomial coefficient. But you can get this closed form from scratch by trying to set up an induction (over $n$) proof, where you realize that you need the relation $c(n,k)= \text{(some factor) } c(n,k-1)$. When you iterate this relation and use $c(n,0)=1$, you get the closed form above which is readily proved by the recurrence.

kunterbunt wrote: Show that \[ c(n,k)=\frac{\prod_{l=1}^n (2^l-1)}{\prod_{l=1}^k (2^l-1)\prod_{l=1}^{n-k} (2^l-1)} \] by plugging it into the recurrence. This is a special case of the $q$-binomial coefficient. But you can get this closed form from scratch by trying to set up an induction (over $n$) proof, where you realize that you need the relation $c(n,k)= \text{(some factor) } c(n,k-1)$. When you iterate this relation and use $c(n,0)=1$, you get the closed form above which is readily proved by the recurrence. @kunterbunt,I don't think its easy enough to realise to use as induction hypothesis.

For the induction step you want to link: \[c(n+1,k)= 2^k c(n,k) + c(n,k-1)\] and \[c(n+1,n+1-k) = 2^{n+1-k}c(n,n+1-k) + c(n,n-k) = 2^{n+1-k}c(n,k-1) + c(n,k).\] Therefore, the missing identity is \begin{align*} 2^k c(n,k) + c(n,k-1) &=2^{n+1-k}c(n,k-1) + c(n,k) \\ \Leftrightarrow (2^k-1) c(n,k) &=(2^{n+1-k}-1)c(n,k-1) \\\Leftrightarrow c(n,k) &=\frac{2^{n+1-k}-1}{2^k-1}c(n,k-1)\end{align*} which leads you directly to the conjecture of the product form of $c(n,k)$ in my above post.

Another nice proof: Since it is required to show that $c(n,k)=c(n,n-k)$ we search for a function of the form $c(n,k)=\frac{F(n)}{F(k)F(n-k)}$ where $F(j)=f(1)f(2) \dots f(j)$ where $f:\mathbb{N}\rightarrow \mathbb{R}$ is a function.If such $f$ exists we are done!! Plugging it into the recurrence we get $f(n+1)=2^kf(n-k+1)+f(k)$ and taking $k=1$ we get the simple recursion $f(n+1)=2f(n)+f(1)$.This is like the famous Tower of Hanoi recursion the solution of which is $f(n)=2^n-1$.Thus we got such an $f$ and so the problem is solved.

Storage 1998 A4 wrote: For any two nonnegative integers $n$ and $k$ satisfying $n\geq k$, we define the number $c(n,k)$ as follows: - $c\left(n,0\right)=c\left(n,n\right)=1$ for all $n\geq 0$; - $c\left(n+1,k\right)=2^{k}c\left(n,k\right)+c\left(n,k-1\right)$ for $n\geq k\geq 1$. Prove that $c\left(n,k\right)=c\left(n,n-k\right)$ for all $n\geq k\geq 0$. We claim that $c(k+r, k)=\frac{(2^{k+1}-1) \dots (2^{k+r}-1)}{(2^1-1)\dots (2^r-1)}$ for all $k, r \geqslant 1$. Indeed, this holds for base cases, and for the induction step, one simply verifies the identity (for $n=k+r$) $$2^k \cdot \left( \frac{(2^{k+1}-1) \dots (2^{k+r}-1)}{(2^1-1)\dots (2^r-1)}\right)+\left(\frac{(2^{k}-1) \dots (2^{k+r}-1)}{(2^1-1)\dots (2^r-1)(2^{r+1}-1)} \right)=\left(2^k+\frac{2^k-1}{2^{r+1}-1} \right) \cdot \left(\frac{(2^{k+1}-1)\dots (2^{k+r}-1)}{(2^1-1)\dots (2^r-1)} \right) $$which indeed satisfies the recursion. Remark. Though this feels unmotivated, I think the easiest way to get this solution is to calculate $c(k+r, k)$ for small values of $r$. For $r=2$, I got a suspicious $3$ in the denominator and a factorised numerator, but when for $r=3$ I got $3 \cdot 7$ in the denominator and same factors continued in the numerator with the additional $(2^{k+3}-1)$ factor, it made sense that all factors on both sides should be of the form $2^{m}-1$ and the range for $m$ is just $1$ through $r$. By plugging this in, we indeed get a solution, as shown above. This is a classic example of small cases being really useful

This seems to be the first purely combinatorial proof in this thread: It's inductively easy to see that $c(n,k)$ is equal to the number of $\{L,R\}$-sequences containing $k$ $R$s and $n-k$ $L$s, where each $L$ can be connected to an arbitrary subset of previous $R$s. Given any such sequence, we can flip all $L$s to $R$s and vice versa. Reading the result backwards gives a valid sequence for $c(n,n-k)$, hence the two quantities are equal.

Dude why i didnt knew the existence of this problem before, its awsome! The construction: Call $P(n,k)$ the assertion of that sequence. With $P(n,1)$ $$c(n+1,1)=2c(n,1)+1 \implies c(n,1)=2^n-1 \; \forall n \in \mathbb Z^+$$Becuase of the induction and becuase $c(1,1)=1$ Now if we try $P(n,2)$ and do some induction xd $$c(n+1,2)=4c(n,2)+2^n-1$$Well now we need to take that $2^n$ out hence we let $c(n,2)=b_n-2^{n-1}$ to get that $b_{n+1}=4b_n-1$ and since $c(2,2)=1$ we have that $b_2=3$ and hence by easy induction we get that $b_n=\frac{2^{2n-1}+1}{3}$ which means that $c(n,2)=\frac{(2^n-1)(2^{n-1}-1)}{3}$ and now we can sus that $c(n,k)=\frac{(2^n-1)(2^{n-1}-1)...(2^1-1)}{((2^k-1)(2^{k-1}-1)...(2^1-1))((2^{n-k}-1)(2^{n-k-1}-1)...(2^1-1))}$ for all $n \ge k \ge 1$ and since this definition follows what is the problem asking us, we will prove that its true by induction. So assume that it holds for $c(n,k-1)$ hence we get $$c(n+1,k)=2^kc(n,k)+\frac{(2^n-1)(2^{n-1}-1)...(2^1-1)}{((2^{k-1}-1)(2^{k-2}-1)...(2^1-1))((2^{n-k+1}-1)(2^{n-k}-1)...(2^1-1))}$$Now i make the replace $c(n,k)=\frac{(2^n-1)(2^{n-1}-1)...(2^1-1)}{((2^k-1)(2^{k-1}-1)...(2^1-1))((2^{n-k}-1)(2^{n-k-1}-1)...(2^1-1))}+L(n,k)$ and now by replacing on the equation and a lot of bashing i'm not gonna write for the sake of my sanity. $$L(n+1,k)=2^kL(n,k) \implies L(n,k)=0 \; \forall n \ge k$$Becuase we have that by the first condition of the problem $L(k,k)=0$ Hence our hypotesis was true meaning that we are done

Induct on $n$ using the fact that \[\frac{c(n,k)}{c(n,k-1)} = \frac{2^{n+1-k}-1}{2^k-1}\]

We claim that \[c(n,k)=\frac{(2^n-1)(2^{n-1}-1)\dots (2^{n-k+1}-1)}{(2^k-1)(2^{k-1}-1)\dots (2^2-1)(2^1-1)}.\]Note that this function does indeed satisfy $c(n,k)=c(n,n-k)$ the same way the binomial function satisfies it. To prove our claim, we will use induction. $~$ Suppose that it is true for $n=r-1$ and any $k$ then for $1\le k\le r-1$ we have \begin{align*} c(r,k) &= 2^k\cdot \frac{(2^{r-1}-1)(2^{r-2}-1)\dots (2^{r-k}-1)}{(2^k-1)(2^{k-1}-1)\dots (2^2-1)(2^1-1)}+\frac{(2^{r-1}-1)(2^{r-2}-1)\dots (2^{r-k+1}-1)}{(2^{k-1}-1)\dots (2^2-1)(2^1-1)}\\ &= \left(\frac{(2^{r-1}-1)(2^{r-2}-1)\dots (2^{r-k+1}-1)}{(2^{k-1}-1)\dots (2^2-1)(2^1-1)}\right)\cdot \left(1+2^k\cdot \frac{2^{r-k}-1}{2^k-1}\right)\\ &= \left(\frac{(2^r-1)(2^{r-1}-1)(2^{r-2}-1)\dots (2^{r-k+1}-1)}{(2^k-1)(2^{k-1}-1)\dots (2^2-1)(2^1-1)}\right) \end{align*}which completes our induction step. Therefore, our claim is true.

lol this is just Gaussian binomial coefficient for $q=2$ Since the starting term and recurrence is same therefore $c(n,k)$ is Gaussian binomial coefficient for $q=2$. since $ c(n,k)=\frac{\prod_{i=1}^n (2^i-1)}{\prod_{i=1}^k (2^i-1)\prod_{i=1}^{n-k} (2^i-1)} $ we're done

Claim: For all $n$, $$c_{n,k}=\prod_{m=1}^k \frac{2^{n+1-m}-1}{2^m-1} \qquad (1)$$whenever $0\leq k\leq n$ (the empty product is, by convention, $1$). Proof. We will prove this by induction. The base cases are easy. Fix $n$ and suppose $(1)$ holds. Note that $$\prod_{m=1}^{n+1} \frac{2^{n+2-m}-1}{2^m-1}=1=c_{n+1,n+1}.$$And for $1\leq k \leq n$, \begin{align*} c_{n+1,k} & = 2^k c_{n,k}+c_{n,k-1} = 2^k \prod_{m=1}^k \frac{2^{n+1-m}-1}{2^m-1}+\prod_{m=1}^{k-1} \frac{2^{n+1-m}-1}{2^m-1} \\ &= \left (\prod_{m=1}^{k-1} \frac{2^{n+1-m}-1}{2^m-1}\right)\left(2^k \frac{2^{n+1-k}-1}{2^k-1}+1\right)= \left (\prod_{m=2}^k \frac{2^{n+2-m}-1}{2^{m-1}-1}\right)\left(\frac{2^{n+1}-1}{2^k-1}\right) = \prod_{m=1}^k \frac{2^{n+2-m}-1}{2^m-1}.\end{align*}This finishes the induction and proves the claim. //// WLOG let $k\leq n$ be such that $n-k<k$. Then $$c_{n,k}=\prod_{m=1}^k \frac{2^{n+1-m}-1}{2^m-1}=\left (\prod_{m=1}^{n-k} \frac{2^{n+1-m}-1}{2^m-1}\right)\left(\prod_{m=n-k+1}^k \frac{2^{n+1-m}-1}{2^m-1}\right)=c_{n,n-k}\cdot \frac{\prod_{m=n-k+1}^k (2^m-1)}{\prod_{m=n-k+1}^k (2^m-1)}=c_{n,n-k}$$as required.