Below is a screenshot from Sedgewick book with exact statement. I understand how to prove it, but what is the intuition behind this? I mean how the author found this fact?
UPD I've come up with the idea:
Any linear combination of general (i.e. not taking into account initial conditions) solutions of this equation is also a solution (that can be checked by substitution, bearing in mind that $f(x, y) = ax + by$). So $a_0 u_n + a_1 v_n$ will be a general solution. And it will also have required initial conditions.
The key concept is linearity. To see how it works, I suggest you make a spreadsheet with your favorite recurrence. The Fibonacci one is a good example, $a_n=a_{n-1}+a_{n-2}$. Make a bunch of columns with this recurrence. If you put $0$ in the top cell ($a_0$) and $1$ in the next cell ($a_1$), you should reproduce the classic Fibonacci sequence. In the next column put $0$ in the top cell and $2$ in the next one. Note that all the numbers are double the first column. Now put $1$ in the top cell and $0$ in the next cell in the second column, $1$ in the top cell and $1$ in the second cell in the third column. Note that all the entries in the third column are the sum of the entries in the first two.
Having seen it in action, you should be able to play with the equations to prove it. To prove $f(a,0)=af(1,0)$ you can proceed by induction. It is true for the first two terms by construction. If it is true for terms up to $k$ it is true for $k+1$ because of the recurrence. Similarly you can prove $f(1,1)=f(1,0)+f(0,1)$ by induction.
This shows that the solutions form a two dimensional vector space. The $f(x,y)$ are the vectors and $\{f(1,0),f(0,1)\}$ is the canonical basis.