0
$\begingroup$

Let sequence $(P_n), (Q_n)$ be defined as $(1),(2),(3)$.

$(1)$ $P_{0} = Q_{0} = 1$
$(2)$ $P_n(x) = P_{n-1}(x) + x^{2^{n-1}} Q_{n-1}(x)$
$(3)$ $Q_n(x) = P_{n-1}(x) - x^{2^{n-1}} Q_{n-1}(x)$

Let k be number of coefficient of $P_n$ which value is 1.
(Example : Let $W(x) = 1x^3 + 2x^2 + 3x + 1$ then $ k = 2$. )

Prove that limit exist $\lim_{n\to\infty} \frac{k}{2^n}$ and calculate it.

  • 0
    Could you please explain what you mean by "Let k be sum of coefficient of $P_n$ which value is 1." Do you mean, let $k$ be the number of coefficients of $P_n$ which are equal to $1$? Or do you mean, let $k$ be the sum of the coefficients of $P_n$? Or do you mean something else?2012-10-14
  • 0
    I think the meaning must be that $k$ is the sum of the coefficients of $P_n$ _or in other words_ $k=P_n(1)$.2012-10-14
  • 0
    Perhaps it's only me but I can't make sense of "let k be sum of coefficient of $\,P_n\,$ which value is 1"?!?2012-10-14
  • 0
    let W(x) = 1x^3 + 5x^2 + 3x + 1, then k = 2 :)2012-10-14
  • 0
    @JohnSmith: So you mean that $k$ is the _number_ of coefficients that are $1$? In that case, start by proving that $P_n$ and $Q_n$ always have degree $2^n-1$, and that ever coefficient of $P_n$ or $Q_n$ is $\pm 1$. You can then get a recurrence out of counting $1$s and $-1$s in $P_n$ and $Q_n$ both.2012-10-14
  • 0
    Yes :) Sorry for my bad description of problem.2012-10-14
  • 0
    Can you write more about your solution? Why ever coefficient of $P_n$ or $Q_n$ is 1 or -1? And than how to compute this limit ?2012-10-14
  • 0
    @JohnSmith: It turns out my wrong solution could be salvaged. (But I'll leave the initial easy induction proofs to you; it's homework after all).2012-10-14

2 Answers 2

1

First a solution that I wrote based on a misunderstanding of the problem (but read on!):

I think the meaning must be that $k$ is the sum of the coefficients of $P_n$ or in other words $k=P_n(1)$.

If that is the case, you don't need to care about the values of the polynomials for $x$s other than $1$, and the recurrence collapses into

  1. $k_0=l_0=1$
  2. $k_n = k_{n-1} + l_{n-1}$
  3. $l_n = k_{n-1} - l_{n-1}$

Since this is a linear recurrence, we can express it as a matrix power: $$ \begin{pmatrix}k_n \\ l_n\end{pmatrix} = > \begin{pmatrix}1&1\\1&-1\end{pmatrix}^n\begin{pmatrix}1\\1\end{pmatrix}$$ The characteristic polynomial of $\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ is $(1-t)(-1-t)-1=t^2-2$, so it has eigenvectors with eigenvalues $\pm\sqrt2$, and $\begin{pmatrix}1\\1\end{pmatrix}$ is some linear combination of them. Therefore $k_n$ will be $a(\sqrt2)^n+b(-\sqrt2)^n)$ for some nonzero $a$ and $b$ that we don't need to calculate explicitly -- the important point is that $\frac{a(\sqrt2)^n}{2^n}$ and $\frac{b(-\sqrt2)^n}{2^n}$ both go towards $0$ no matter what $a$ and $b$ are; therefore $\frac{k_n}{2^n}\to 0$ too.


More elementarily, we can also just compute $(k_n,l_n)$ for the first few $n$s and look for patterns: $$ \begin{array}{c|cc} n & k_n & l_n \\\hline 0 & 1 & 1 \\ 1 & 2 & 0 \\ 2 & 2 & 2 \\ 3 & 4 & 0 \\ 4 & 4 & 4 \end{array}$$ This clearly suggests that $l_{2m}=k_{2m}=k_{2m-1}=2^m$ and $l_{2m-1}=0$, and we can then prove that this is the case by an easy induction.

Now it turned out that the question was not actually about the sum of all coefficients of $P_n$, but about the number of coefficients of $P_n$ that happen to be $1$. But what we have done so far can actually be salvaged. We now start by proving:

  • The degree of $P_n$ and $Q_n$ is always $2^n-1$. (Proof: simultaneous induction on $n$).

  • Every coefficient of $P_n$ and $Q_n$ is $\pm 1$. (Proof: simultaneous induction on $n$, using the previous result in the induction step).

Now the number we're really after is the number of $1$ coefficients in $P_n$. Let's write that as $K_n$ rather than $k_n$ to reduce confusion with the "wrong" $k_n$ in the above calculation. Because all coefficients are either $1$ or $-1$, we have $$ P_n(1) = -2^{n} + 2K_n $$ where the $-2^n$ term assumes that all coefficients are $-1$ and $2K_n$ corrects for those that are actually $+1$. Solving for $K_n$ gives $$ K_n = \frac{P(1)+2^n}{2} $$ So the limit we're after is $$ \lim_{n\to\infty} \frac{K_n}{2^n} = \lim_{n\to\infty} (\frac{O(\sqrt 2^n)}{2^n} + \frac12) = \frac 12 $$ where we use $P(1)=O(\sqrt 2^n)$ from the above solution-to-the-wrong-question.

So the sought-for limit is $\frac 12$.

2

The polynomials $P_n,Q_n$ are called Shapiro polynomials and the sequence $k_n=P_n(1)$ defined by Henning Makholm is $k_n=s_{2^n-1}$ where $s_k$ is the Rudin–Shapiro sequence. The proof of $\displaystyle{\lim_{n \to \infty}\frac{k_n}{2^n}=0} $ can be deduced from the last proposition here but of cource Makholm's solution is more elementary. Some interesting facts about Rudin–Shapiro sequence can be found here and a more difficult problem about them here.

  • 0
    Excuse me, is this limit correct? Makhlom's solution is $1/2$ and yours 0 ? Which is right?2012-10-14
  • 0
    I am referring to the sequence $k_n=P_n(1)$ as the sequence with corresponding limit $0$. Now, your sequence $k_n$ is defined by Makhlom as $K_n$ and he explained why $K_n=\frac{k_n+2^n}{2}$. This is the one with corresponding limit $\frac{1}{2}$.2012-10-14
  • 0
    Ok, thanks !!! :)2012-10-14