# Proving Linear Independence of Sequences

Good morning,

my question is about proving the linear independence of sequences. In the theory of linear difference equations, one needs a fact, that for all distinct $\lambda_1,\ldots,\lambda_m \in \mathbb{C}$ and all $k_1,\ldots,k_m \in \mathbb{N}$, the functions (sequences) $$n^{0} \lambda_1^n, n^1 \lambda_1^n, \ldots, n^{k_1 - 1} \lambda_1^n,$$ $$n^{0} \lambda_2^n, n^1 \lambda_2^n, \ldots, n^{k_2 - 1} \lambda_2^n,$$ $$\ldots,$$ $$n^{0} \lambda_m^n, n^1 \lambda_m^n, \ldots, n^{k_m - 1} \lambda_m^n$$ are linearly independent. Although this fact is extensively used in literature, I haven't found any satisfactory proof and my attempts to prove this by myself weren't successful as well.

I know how to prove that $\lambda_1^n,\lambda_2^n,\ldots,\lambda_m^n$ are linearly independent for distinct $\lambda_1,\ldots,\lambda_m \in \mathbb{C}$ (using Vandermonde determinant). Moreover, I know how to prove that $n^0 \lambda_i^n, n^1 \lambda_i^n, \ldots, n^{k_i - 1} \lambda_i^n$ are linearly independent (if one supposes that they are dependent, one gets an equation that says that a polynomial with at least one non-zero coefficient is zero for all $n \in \mathbb{N}$, i.e., a contradiction). But I don't know how to combine these results. Simply the fact that both sets of sequences are linearly independent does not prove that their union is linearly independent. Any ideas would be helpful.

Thank you in advance.

You can get linear independence quite easily by looking at growth rates (analytic considerations rather than algebraic identities). Your list is very easily seen to fall into the category below.

Any set of (say, positive) functions $f_1(n), \ldots, f_k(n)$ satisfying $f_i = o(f_j)$ for all $1 \le i<j\le k$ must be linearly independent. Suppose there were a non-trivial linear combination $\sum_{i=1}^k c_i f_i = 0$, and WLOG $c_k=1$. Then choose $n$ large enough so that $f_k(n) > \sum_{i<k} |c_i|\, f_i(n)$. Contradiction.

EDIT: As pointed out by anon, the question calls for $\lambda_i \in \mathbb C$, in which case it's quite possible for members of this family to be comparable in size. However, this argument allows one to decompose the entire family into small sets with matching growth rates, and those can be handled by Vandermonde.

• Thanks for pointing this out! I didn't notice the $\lambda_i \in \mathbb C$. – Erick Wong Jun 21 '12 at 8:50
• You don't need $f_i$ to be positive; it's fine if they're complex-valued and $|f_i|=o\big(|f_j|\big)$ for $1\le i<j\le k$. Then we can get a contradiction on $$|f_k(n)|>\sum_{i<k}|c_if_i(n)|\ge\left|\sum_{i<k}c_if_i(n)\right|$$ (I say this because OP set $\lambda_i\in\Bbb C$.) – anon Jun 21 '12 at 8:50
• Well I see now. Thanks a lot! – 042 Jun 21 '12 at 9:04