0
$\begingroup$

Let $$f(x) = \sum_{n\geq 0} a_n x^n = \frac{P(x)}{(1-x)^d}$$ be a rational function.

(a) Prove: There is a polynomial $P_2(x)$ so $$\sum\limits_{n\geq 0} a_{2_n} x^n = \frac{P_2(x)}{(1-x)^d}$$

(b) Let $r \geq 1 \in \mathbb{N}$. Show that an polynomial $P_r$ exists so that $$\sum_{n\geq 0} a_{rn} x^n = \frac{P_r(x)}{(1-x)^d}$$

Hint: Use the $r$th roots of unity which are defined by $\exp\left(\large \frac{2\pi ik}{r}\right), 0 \leq k \leq r - 1$.


(a) I don't know what this d is about (and no one else did). Might be an absolute term.

As $f(x)$ is a rational function, it can be defined as a fraction of two polynomials $\large \frac{P(x)}{Q(x)}$. But that is unfortunately all I know about this.

Could you please help me going on?

(b) I don't know how the $r$th roots of unity (and therefore numbers $x$ for which applies: $x^r = 1$) can help me solving this? I don't find any approach.

Could you please help me a bit?

Thanks in advance!

  • 0
    @muffel: The wording could be better, it should say instead let $P(x)$ be a polynomial. If you quoted the beginning of the problem correctly, you are absolutely right to be confused. There is a TeX error in the first displayed equation. It is possible to guess what is intended, but it really should be fixed.2011-06-17
  • 0
    In my edit, I didn't change the TeX of the stated equations in (a), (b)...I'll leave that to you @muffel, to correct as needed.2011-06-17
  • 0
    @muffel...cont. nor in the top equation (did I make any TeX changes).2011-06-17
  • 0
    The denominator in the right side of (a) should be $(1 - x^2)^d$, and in (b) it should be $(1 - x^r)^d$.2011-06-17
  • 0
    @Robert-Israel I asked the author of this and he confirmed it's $(1-x)^d$ both times.2011-06-17
  • 0
    @Robert Israel: It is hard to track through the changes that have been made in the first sum. But if we calculate $(f(x)+f(-x))/2$, we get something that involves only even powers of $x$. Then replace $x^2$ by $x$. I would prefer if the question had on the left and right, $u$, as in $\sum a_{2n} u^n$.2011-06-17

2 Answers 2

1

For (a), try comparing $f(-x)$ and $f(x)$. This should give you some idea how to use the hint in given in (b).

  • 0
    @Steve what does comparing $f(-x)$ and $f(x)$ or rather $\frac{P(x)}{(1-x)^d}$ and $\frac{-P(x)}{(1-x)^d}$ have to do with (b)?2011-06-18
  • 0
    When Steve says $f(-x)$ and $f(x)$, he means $f(-x)$ and $f(x)$. I don't know where you get the idea that he means $P(x)/(1-x)^d$ and $-P(x)/(1-x)^d$.2011-06-19
  • 0
    @Steve @Gerry-Myerson Oops, no idea what the hell came over me.. Sorry! Of course it's $\frac{P(x)}{(1-x)^d}$ compared to $\frac{P(x)}{(1+x)^d}$ respectively $\sum_{n\geq 0} a_n (-x)^n$. The *r* th roots can turn some values into 1, but I still don't see the relation to showing the existence of a polynomial $P_r$ in general.2011-06-19
  • 0
    @muffel, let's look at $r=3$. $f(x)=a_0+a_1x+a_2x^2+\dots$. $f(\zeta x)=a_0+a_1\zeta x+a_2(\zeta x)^2+a_3(\zeta x)^3+\dots=a_0+a_1\zeta x+a_2\zeta^2x^2+a_3 x^3+\dots$. Do the same thing for $f(\zeta^2x)$. Then add 'em up: $f(x)+f(\zeta x)+f(\zeta^2x)$ on the left side of the equation, and what do you get on the right side when you add the three power series?2011-06-20
  • 0
    @Gerry-Myerson $f(\zeta^2x) = a_0 + a_1 \zeta^2 x + a_2 x^2 + a_3 x^3 + \cdots$. The sum $f(x) + f(\zeta x) + f(\zeta^2 x) = 3 a_0 + a_1x(1+\zeta+\zeta^2) + a_2 x^2(2 + \zeta^2) + 3 a_3 x^3$. What I still don't get: I am looking for a polynomial that can be represented by $\frac{P(x)}{(1-x)^d}$, but what does this have to do with the roots of unity. This term looks similar to the sum of infinite geometric series, but he power of *d* is annoying then.2011-06-20
  • 0
    ok, I really need to be more precise: Of course I am looking for a polynomial $P_r(x)$ for which applies $\frac{P_r(x)}{(1-x)^d} = \sum_{n\geq 0} a_{rn} x^n$2011-06-20
  • 0
    @muffel, you've written $1+\zeta+\zeta^2$, but after our previous discussion, you know what this is. You've written $2+\zeta^2$ for the coefficient of $x^2$, but this is wrong. You've made the sum appear to end with the $x^3$ term, which it doesn't, it goes on forever, but with a pattern that should become apparent to you if you calculate enough of it and do it right. When you've finished that, we'll get back to your $P(x)/(1-x)^d$. By the way, don't you have a teacher or tutor or someone you can go to for help?2011-06-20
  • 0
    @Gerry-Myerson I do have a tutor - unfortunately she doesn't really better get on with this than I do. All she does is hand us the standard solutions. We may ask questions but don't get them answered in any way it could help us. And as I am not able to understand this only by the lecture and the few books I have I am hoping (quite successfully yet thanks to guys like you) to get the rest done in any way...2011-06-22
3

Here's what you need to know about roots of unity. Let $\zeta=e^{2\pi i/r}$. Then the $r$th roots of unity are the numbers $1,\zeta,\zeta^2,\dots,\zeta^{r-1}$. Let $m$ be some integer, and raise all these numbers to the power $m$, and add them: $1+\zeta^m+\zeta^{2m}+\cdots+\zeta^{(r-1)m}$. That's the sum of a geometric progression. If $m$ is a multiple of $r$ then each term in the sum is 1 so the sum is $r$. If $m$ is not a multiple of $r$ then you should check that the formula for the sum of a geometric progression tells you that the sum is zero.

OK?

  • 0
    Myerson Barely. First of all: What about the *k* in the definition of the roots of unity - why could you drop it? When writing down the *r* th roots of unity you used powers instead of subscript indexes - these aren't actually powers, are they? I do understand that if *m* is a multiple of *r* the sum is *r*. But how might $\frac{a}{1-r}$ show that the sum is 0 otherwise? And how might this all help me showing that a polynomial $P_r$ exists?2011-06-18
  • 0
    @muffel, about the $k$: exp$(2\pi ik/r)=e^{2\pi k/r}=(e^{2\pi i/r})^k=\zeta^k$. Yes, the powers of $\zeta$ are the $r$th roots of unity. $a/(1-r)$ is the formula for the sum of an *infinite* geometric progression, but what we have here is a *finite* geometric progression, with $r$ terms - do you know the formula for that sum? When Steve said compare $f(-x)$ and $f(x)$, he could have suggested you add those two functions to see what happens. Do that, then put your observation together with what I've said about roots of unity to see what you can do about (b).2011-06-19
  • 0
    @Gerry-Myserson ok, considering $1 + \zeta^m + \cdots + \zeta^{(r-1)m}$ as a geometric progression from 0 to $(r-1)$ with a scale factor $a = 1$ and a common ratio $r = \zeta^m$. Then using $\sum_{i = 0}^n a\cdot r^i = \frac{a(1-r^{n+1})}{1-r})$ here applies $\sum_{n = 0}^{r-1} \zeta^n = \frac{1-\zeta^{r*m}}{1-\zeta^m}$, correct? But why is this $0$ if $m$ is not a multiple of $r$?2011-06-19
  • 0
    @muffel, the numerator contains the term $\zeta^{rm}=(\zeta^r)^m=1^m=1$. And please try to spell my name correctly.2011-06-20
  • 0
    Myerson Sorry!2011-06-20