Let $n$ be a positive integer. Consider the sum $x_1y_1 + x_2y_2 +\cdots + x_ny_n$, where that values of the variables $x_1, x_2,\ldots, x_n, y_1, y_2,\ldots, y_n$ are either 0 or 1. Let $I(n)$ be the number of 2$n$-tuples $(x_1, x_2,\ldots, x_n, y_1, y_2,\ldots, y_n)$ such that the sum of the number is odd, and let $P(n)$ be the number of 2$n$-tuples $(x_1, x_2,\ldots, x_n, y_1, y_2,\ldots, y_n)$ such that the sum is an even number. Show that: \[ \frac{P(n)}{I(n)}=\frac{2^n+1}{2^n-1} \]
Problem
Source: Spanish Communities
Tags: combinatorics unsolved, combinatorics
zgorkster
30.04.2006 20:02
I put a solution here: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=84880
goodar2006
02.10.2011 08:36
also we can solve it using recurrences $P(n)=3P(n-1)+I(n-1)$ and $I(n)=3I(n-1)+P(n-1)$ and this fact that $P(n)+I(n)=2^{2n}$.
RMACR7LP
10.12.2017 06:47
We proceed by induction. Call $S_n$ the sum defined above. Suppose $n=1$ so $S_1=x_1y_1$ from this, we get that the pairs $(x_1,y_1)$ that make $S_1$ even are ${(0,0), (0,1), (1,0)}$ and the one that makes it odd is $(1,1)$ thus, $P(1)=3=2^1+1$ and $I(1)=1=2^1-1$, so its true for $n=1$. Suppose it holds for $n=k$. Note that $S_{k+1}=S_k +x_{k+1}y_{k+1}$, from this we get $P(k+1)=3P(k)+I(k)$ since there are three options of $x_{k+1}y_{k+1}$ that make $ S_{k+1}$ even provided that $S_k$ is even and one option of the pair that makes it even provided that $S_k$ is odd. Using the same argument we get $I(k+1)=P(k)+3I(k)$. From the induction hypothesis we get,
\[\frac{P(k+1)}{I(k+1)}=\frac{3P(k)+I(k)}{P(k)+3I(k)}=\frac{(3(\frac{2^k+1}{2^k-1})+1)I(k)}{(\frac{2^k+1}{2^k-1}+3)I(k)}\]
With a little bit of algebra the result follows for $k+1$ and we're done.
[\hide]