On Puzzle Exchange I already found this answer great: https://puzzling.stackexchange.com/a/6431/8863
Currently I there are two steps I don't yet understand. For example the connectin between characteristic polynominals and recurrence relations.
I find this topic well researchable and study on my own.
However I cannot follow the reasoning:
If we assume $p\neq\frac{1}{2}$, this polynomial has two distinct roots: $$ r=1,\hspace{1cm} r=\frac{p}{1-p}. $$ This means that $d(x)$ has the form $$ d(x)=c_1+c_2\left(\frac{p}{1-p}\right)^x, $$
Where does the letter form come from? I see there are in fact both roots used. I guess the "full" form would be: $ d(x) = c_1 r_1^x + c_2 r_2 ^x $, with $r_1, r_2$ being the just found roots. Is there a name for this step (+ proof!), coming from the roots of the characteristic polynominal to a closed form? I have just found:
http://mathcircle.berkeley.edu/BMC3/Bjorn1/node6.html
But sadly no proof provided :Z