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!

Improve this question
$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Jun 17 '11 at 21:04
  • $\begingroup$ 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. $\endgroup$ – amWhy Jun 17 '11 at 21:09
  • $\begingroup$ @muffel...cont. nor in the top equation (did I make any TeX changes). $\endgroup$ – amWhy Jun 17 '11 at 21:32
  • $\begingroup$ The denominator in the right side of (a) should be $(1 - x^2)^d$, and in (b) it should be $(1 - x^r)^d$. $\endgroup$ – Robert Israel Jun 17 '11 at 21:41
  • $\begingroup$ @Robert-Israel I asked the author of this and he confirmed it's $(1-x)^d$ both times. $\endgroup$ – muffel Jun 17 '11 at 21:53
1
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ @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)? $\endgroup$ – muffel Jun 18 '11 at 22:15
  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Jun 19 '11 at 1:29
  • $\begingroup$ @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. $\endgroup$ – muffel Jun 19 '11 at 17:03
  • $\begingroup$ @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? $\endgroup$ – Gerry Myerson Jun 20 '11 at 1:08
  • $\begingroup$ @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. $\endgroup$ – muffel Jun 20 '11 at 9:07
3
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – muffel Jun 18 '11 at 22:47
  • $\begingroup$ @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). $\endgroup$ – Gerry Myerson Jun 19 '11 at 1:27
  • $\begingroup$ @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$? $\endgroup$ – muffel Jun 19 '11 at 17:23
  • $\begingroup$ @muffel, the numerator contains the term $\zeta^{rm}=(\zeta^r)^m=1^m=1$. And please try to spell my name correctly. $\endgroup$ – Gerry Myerson Jun 20 '11 at 0:58
  • $\begingroup$ Myerson Sorry! $\endgroup$ – muffel Jun 20 '11 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.