Let $\lambda_1,\ldots,\lambda_k$ and $\alpha_1,\ldots,\alpha_k$ be real numbers and suppose we define a sequence by the recurrence relation $$a(n) = \sum_{i=1}^{k} \lambda_i a(n-i) \tag{1}$$
With initial conditions $$a(n) = \alpha_n \text{ for }i=1,\ldots,k \tag{2}$$
If $r = r(n)$ and $g=g(n)$ are sequences that satisfies (1), then $r+a\ g = r(n) + a\ g(n)$ also satisfies (1):
$$r(n) + a \ g(n) = \sum_{i=1}^{k} \lambda_i r(n-i) + a \ \sum_{i=1}^{k} \lambda_i g(n-i) = \sum_{i=1}^{k} \lambda_i (r(n-i)+a\ g(n-i))$$
So the space of all functions from $\mathbb{N}$ to $\mathbb{C}$ (I'll explain using complex later) that satisfies (1) has the property that every linear combination is also a solution. Since we can define a neutral element and opposite element for every sequence that satisfies (1), we say the set of all the functions satisfying (1) has the structure of a vector space.
The main idea of solving a linear recurrence is finding a suitable basis for this space, that is, a minimal set $B \subset V$ such that every element of $V$ is a linear combination of elements of $B$. The dimension of this space (i.e. the size of the basis) can be shown to be $k$, but I can't think of any elementary method.
So the problem reduces to finding a suitable basis!
Suppose that for some $u \in \mathbb{C}$ we have $b(n)= u^n \in V$.
So, $b$ satisfies (1): $$u^n = \sum_{i=1}^{k} \lambda_i u^{n-i}$$ And let assume that $u \neq 0$, then we have $$u^k = \sum_{i=1}^k \lambda_i u^{k-i}$$
So, if we solve the polynomial in u:
$$u^k - \lambda_1 u^{k-1} + \cdots - \lambda_{k-1}u - \lambda_{k}=0 \tag{3}$$
By the fundamental theorem of algebra (now, we need $\mathbb{C}$ here!), we now that (3) has $k$ or less roots.
We call (3) the characteristic equation of recurrence (1)
Assume that (3) has $k$ different roots $u_1, \ldots, u_k$, then each $b_i = (u_i)^n$ is a solution.
If (3) has less than $k$ solutions, let $u$ be a solution of multiplicity $m$, then $b(n) = u^n$ is a solution but also $c_j = n^j u^j$ for $j=1,\ldots,m-1$, so this solve the problem completely, because we alredy found a basis having $k$ elements (check it!), and using (2), we can find a unique solution to our recurrence relation