Deriving recurrence relation for combination formula 
From this generating function $$\sum\limits_{k=0}^n C(n,k) t^{k} = (1+t)^{n}$$ and
  the observation that $$(1+t)^{n+1} = (1+t)(1+t)^{n}$$ we can equate
  like powers of $t^{k}$ on both sides (since the powers of $t$ are
  linearly independent) to get the important relation 
  $$C(n+1,k) = C(n,k) + C(n,k-1)$$

$C(n,k)$ represents the formula for combinations. 

I'm reading a textbook and I'm having trouble following the steps the author goes through here. 


*

*A general explanation would help.

*What does "the powers of $t$ are linearly independent" mean?

*How does this compare to the recurrence relation $C(n+1,k)=\frac{(n+1)}{(n+1-k)}C(n,k)$? They are equivalent, but I don't really see the connection.

 A: The Binomial Theorem gives
$$\sum\limits_{k=0}^n C(n,k) t^{k} = (1+t)^{n}\qquad\qquad\qquad\qquad\text{(1)}$$
Then
\begin{eqnarray*}
(1+t)^{n+1} &=& (1+t)(1+t)^{n} \\
\sum\limits_{k=0}^n C(n+1,k) t^{k} &=& (1+t)\sum\limits_{k=0}^n C(n,k) t^{k}\qquad\qquad\qquad\text{by applying (1) to both sides} \\
&=& \sum\limits_{k=0}^n C(n,k) t^{k} + \sum\limits_{k=0}^n C(n,k) t^{k+1} \\
\end{eqnarray*}
The LHS coefficient of $t^k$ is $C(n+1,k)$.
The RHS coefficient of $t^k$ is $C(n,k) + C(n,k-1)$. Thus, these expressions are equal for any $k=0,1,...,n$.
"Powers of $t$ are linearly independent" means that it is impossible to have $t^k$ equal to any linear combination of the other powers of $t$, for all $t$. That is,
there are no constants $a_0, a_1, \ldots, a_{k-1}, a_{k+1}, \ldots, a_n$ such that for all $t$ we have
$$t^k = a_0t^0 + a_1t^1 + \cdots + a_{k-1}t^{k-1} + a_{k+1}t^{k+1} + \cdots + a_nt^n.$$
This linear independence is pretty obvious, actually, and doesn't really need stating, IMO.
As for the recurrence relation $C(n+1,k)=\frac{(n+1)}{(n+1-k)}C(n,k)$, sorry, I don't what you mean by equivalence to the one above: they are both true in their own right.
