There is a famous problem, given that a man has a number of daughters and if you were to meet two of them at random there is a 50% chance that both have blue eyes. How many daughters does the man have? One way to find the solution is to find integer solutions to the equation:
$\frac{b (b-1)}{d (d-1)}=\frac{1}{2}$
We can turn this into a quadratic as a function of blue-eyed daughters, b:
$b^2-b-\frac{1}{2} d (d-1)=0$
Using the quadratic formula, our solutions will be integers of the form:
$\frac{1}{2} \left(1+\sqrt{1+2 d (d-1)}\right)$
Thus, the number of daughters, d, will be such that $1+2 d (d-1)$ is a square number with a root that is odd. For example, if d is 4, then $1+2 d (d-1)$ is 25, whose root is 5, an odd number, hence a solution. The next possible value for d is 21.
All well and good, but this seems like an extravagant method to me, and moreover, at the end I had no regular answer, but was stuck plugging in test values for d to see which would result in odd roots.
My intuition is that it may be possible to solve the problem and find the sequence of all possible numbers of daughters using a generating function, but my skill at mathematics is not up to this challenge.
Is there anyone who can tell me how to derive the generating function which expresses all the solutions for the problem of the blue-eyed daughters (or can suggest a better method)?
Write $1+2d(d-1)=y^2$. Multiply through by $2$, and complete the square. Letting $2d-1=x^2$, we arrive at the Pell Equation $x^2-2y^2=-1$.
This has fundamental solution $x_0=1$, $y_0=1$. It turns out that the general solution in positive integers $(x_n,y_n)$ is given by $x_n+y_n\sqrt{2}=(1+\sqrt{2})^{2n+1}$. Thus $$x_{n+1}+y_{n+1}\sqrt{2}=(x_n+y_n\sqrt{2})(3+2\sqrt{2}).$$ That gives the recurrences $$x_{n+1}=3x_n+4y_n,\qquad y_{n+1}=2x_n +3y_n.$$ We are only really interested in $x_n$. From the above recurrences we can get a second-order linear recurrence for $x_n$ with constant coefficients. We get $x_{n+2}=6x_{n+1}-x_n$. This recurrence can be solved using the ordinary techniques, which include generating functions.