Number of descendants at the Nth generation. Absurd result... :( Are we all the descendants of Charlemagne?
The assumption seems logical but I was wondering if I could calculate the probability, or maybe just the number of descendants at the Nth generation. But it‘s complicated. So here‘s a simplified version:
A group of 4 people: A, B, C and D. 
Each generation, two couples are formed (there are 3 possibilities: AB/CD, AC/BD and AD/BC)
These couples have children together (between 0 and 4).
The next generation is also 4 members strong. Each member of the new generation has an equal probability of being the child of the first couple or of the second. 
The same process is repeated.
What is the probability of being a descendant of A at the Nth generation?
If I break it up, I would say that at:


*

*Generation 0 (G0) there is only A, so a 25% chance. 

*Generation 1 (G1): every child has an equal probability of being the child of A or of the other couple. So a 50% chance.

*Generation 2 (G2): every member of the group of G1 has a 50% chance of not being a descendant of A. When I pair two of them randomly together, they have a 25% chance of neither of them being a descendant of A. So each member of G2 has a 75% chance of being a descendant of A.

*Generation N (Gn): if you go on this way, it‘s easy to see the probability rises to 100%...
....BUT.........
There is a 6.25% probability that NO person in G1 is the descendant of A. In that case, the probability of there not being ANY descendant of A in the Nth generation, MUST be superior to 6.25%!! How come then are we finding it to be 0%??!!
What is wrong here??!!
Thanks a lot in advance!
 A: Joriki's analysis looks convincing, but skips somewhat quickly past what is wrong with your analysis:

Generation 2 (G2): every member of the group of G1 has a 50% chance of not being a descendant of A. When I pair two of them randomly together, they have a 25% chance of neither of them being a descendant of A. So each member of G2 has a 75% chance of being a descendant of A.

So far so good. Each person in G1 has randomly chosen either the A-nonA couple or the nonA-nonA couple as his parents, so the "A-ness" of two randomly chosen persons in G1 is independent.
Without this independence your "25% chance" wouldn't necessarily hold.

Generation N (Gn): if you go on this way, it‘s easy to see the probability rises to 100%...

Here it goes wrong if you repeat your analysis from G2 because "mother not descended from A" and "father not descended from A" are no longer independent -- in particular your cannot multiply their probabilities to find the probability of your ancestors being A-free.
On the contrary, in late generations it becomes overwhelmingly likely that either everyone descends from A or nobody does. Thus with high probability, two randomly chosen persons have the same A-ness, which means that the A-ness of your mother and father will be highly correlated.
A: Turn it around.  I have two parents, four grandparents, eight great grandparents and so on.  If we go back $30$ generations I would have $2^{30} \approx 1$ billion ancestors.  $600$ years ago there were not a billion people on earth, so many of those ancestors must be the same people.  If you assume much mixing at all, I must be descended from everybody alive in the year $1200$.  
There are two holes in this analysis.  One, some of the people did not have any children, so I am not descended from them.  Two, there could be isolated groups who do not mix with the general population.  A European of $800$ could do the same calculation and claim to be descended from everybody alive in $400$ or some such year.  As far as we know there was no mixing with the inhabitants of the Americas during that period and probably none with some other remote areas.
