1
$\begingroup$

I am confused, as not clear except by multiplying both terms on the r.h.s, and showing that all cancel out except the two on the l.h.s., as below:

$(x)(x^{k-1}+x^{k-2}+\ldots+1) - (x^{k-1}+x^{k-2}+\ldots+1)= x^k -1$

$\endgroup$

closed as unclear what you're asking by Andrés E. Caicedo, The Phenotype, Did, Ethan Bolker, zoli Feb 19 '18 at 18:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ So RHS = LHS. What's your question then? $\endgroup$ – Math Lover Feb 19 '18 at 16:29
  • $\begingroup$ @Math Lover A better proof, even if uses complex topics. I mean that intuitively one should be able to understand it. I might be completely wrong, but the polynomial multiplication or division (as in the next comment) gives no intuitive feel to me. $\endgroup$ – jitender Feb 19 '18 at 16:30
  • 1
    $\begingroup$ try to long divide $x^k-1$ with $x-1$ .. $\endgroup$ – user2277550 Feb 19 '18 at 16:33
  • 1
    $\begingroup$ I'm assuming this is for an intro number theory class. You're going to want to use the euclidean algorithm generalized for polynomials. $\endgroup$ – EDZ Feb 19 '18 at 16:50
  • 1
    $\begingroup$ you can show that they agree at k distinct points ($k$ roots of unity) in $\mathbb C$ and thus are equal. But, really try to get used to the euclidean algorithm and it's consequences. Very important for more advanced topics. $\endgroup$ – EDZ Feb 19 '18 at 16:55
2
$\begingroup$

Here's another approach using roots of unity and the fundamental theorem of algebra.

The zeros of $x^k - 1$ are $\{e^{\frac{n2\pi i}{k}}\}$ for $0 \leq n < k$.

Therefore, we can rewrite $x^k - 1$ as:

$$x^k - 1 = M\prod_{n=0}^{k-1} (x-e^{\frac{n2\pi i}{k}})$$

for some $M$

Now, let's find the zeros of $P(x) = (x-1)(x^{k-1} + ... + 1)$

Clearly, $x = 1 = e^{\frac{0*2\pi i}{k}}$ is a zero.

What about $Q(x) = (x^{k-1} + ... + 1)$?

Let's substitute our $k-1$ roots of unity, $r_n$ where $n > 1$

$$Q(r_n) = \sum_{j=0}^{k-1} (r_n)^j = \sum_{j=0}^{k-1} (e^{\frac{n2\pi i}{k}})^j = \frac{1 - (e^{\frac{n2\pi i}{k}})^k}{1 - e^{\frac{n2\pi i}{k}}} = \frac{0}{1 - e^{\frac{n2\pi i}{k}}} = 0$$

Using the sum of a finite geometric series and the fact that: $(e^{\frac{n2\pi i}{k}})^k = e^{n2\pi i} = 1^n$

Therefore, we can rewrite $Q(x)$ as:

$$Q(x) = D' \prod_{n=1}^{k-1} (x-e^{\frac{n2\pi i}{k}})$$

and $P(x)$ as:

$$P(x) = D\prod_{n=0}^{k-1} (x-e^{\frac{n2\pi i}{k}})$$

for some constant $D$.

Now, we have that $P(x)$ agrees with $x^k - 1$ at $k$ points, which are the $k$ roots of unity.

However, we also have that $P(0) = -1$ and $0^k - 1 = -1$ We can sub this back into the factored expressions to see that $M = D$, or we can also conclude that because $(x-1)(x^{k-1} + ... + 1)$ and $x^k - 1$ agree at $k + 1$ distinct points, $(x-1)(x^{k-1} + ... + 1) = x^k - 1$ for all $x$.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for the answer. I am following your advice in comments to the post, but this approach is base to help find answers to all questions stated by me there, and elsewhere. $\endgroup$ – jitender Feb 19 '18 at 17:46
7
$\begingroup$

For fun:

Let $x$ be real, and consider the geometric series:

1)$\sum_{i=0}^{k-1} x^i = 1+x +x^2 +..+x^{k-1};$

2) $ x \sum_{i=0}^{k-1}x^i = \ \ x+x^2+...+x^{k-1} +x^k;$

Subtract : 2)-1):

$(x-1)\sum_{i=0}^{k-1} x^{i}= x^k-1$.

$\endgroup$
  • $\begingroup$ Is it possible to generalize by this way to other identities, which can be based upon it. Although, I am not able to find more identities in text that can be based upon it, but can imagine. Say,the easiest would be : $x^k-a^k$. $\endgroup$ – jitender Feb 19 '18 at 16:52
  • 1
    $\begingroup$ jitender. What do you have in mind? $\endgroup$ – Peter Szilas Feb 19 '18 at 16:54
  • $\begingroup$ Polynomial has components that is given by sum of terms, which in turn can be formed by multiplication or division, my earlier comment states as a simplest extension. I want to view polynomials that generalises and makes it POSSIBLE to know which form is possible & which not. $\endgroup$ – jitender Feb 19 '18 at 16:57
  • 1
    $\begingroup$ Not an expert. The above works for x^k-1( 1!!!) If you have x^k-a^k , a factor is (x-a) reduces polynomial by 1 degree.Do not know anything more specific. $\endgroup$ – Peter Szilas Feb 19 '18 at 17:27
2
$\begingroup$

This one cries out for a simple proof by induction:

If $k = 1$ we evidently have

$x^1 - 1 = (x^1 - 1)(1), \tag 1$

and if $k = 2$:

$x^2 - 1 = (x -1)(x + 1) = (x - 1)\left ( \displaystyle \sum_0^1 x^i \right ); \tag 2$

if we now suppose that the formula holds for some positive $m \in \Bbb Z$,

$x^m - 1 = (x - 1) \left ( \displaystyle \sum_0^{m - 1} x^i \right ), \tag 3$

then

$x^{m + 1} - 1 = x^{m + 1} - x^m + x^m - 1$ $= x^m(x - 1) + (x - 1) \left ( \displaystyle \sum_0^{m - 1} x^i \right ) = (x - 1) \left ( x^m + \displaystyle \sum_0^{m - 1} x^i \right ) = (x - 1) \left ( \displaystyle \sum_0^m x^i \right ), \tag 4$

which shows that the formula

$x^k - 1 = (x - 1) \left ( \displaystyle \sum_0^{k -1} x^i \right ) \tag 5$

is valid for all positive integers $k$.

$\endgroup$
  • 1
    $\begingroup$ Thanks, although I am still analyzing this approach. Although, it may be vague, but will it generalize to checking all POSSIBLE forms of polynomial identities that can be generated. Also, the next question would be: if this approach would help in viewing polynomials, if possible; or need some analytical approach to that as stated in the last comment by @EDZ ; and this approach is good for verifying only the POSSIBLE identities. $\endgroup$ – jitender Feb 19 '18 at 17:13
  • 1
    $\begingroup$ @jitender: well, one thing I like about this approach is that it (in common with the other answers) shows that the identity holds in $R[x]$, the ring of polynomials over an arbitrary (unital) ring $R$. So avoiding the complex root of unity approach is good from that perspective, although that way of doing things certainly leads in some fascinating directions. And certainly there are plenty of polynomial identities which may be established by induction, viz, $x^n - y^n = (x - y)\sum_0^{n - 1} x^i y^{n - i - 1}$, which is a direct generalization of the present identity. $\endgroup$ – Robert Lewis Feb 19 '18 at 17:26
1
$\begingroup$

It's like this: $(x-1)(x^{k-1}+x^{k-2}+\ldots+1)$

$=x(x^{k-1}+x^{k-2}+\ldots+1) - (x^{k-1}+x^{k-2}+\ldots+1)$

$=x^{k-1+1}+x^{k-2+1}+x^{k-3+1}+x^{k-4+1}...+x^3+x^2+x-x^{k-1}-x^{k-2}-x^{k-3}-...-x-1$

$=x^{k}+x^{k-1}+x^{k-2}+x^{k-3}...+x^3+x^2+x-x^{k-1}-x^{k-2}-x^{k-3}-...-x^2-x-1$

$=x^{k}+(x^{k-1}+x^{k-2}+x^{k-3}...+x^3+x^2+x)-(x^{k-1}+x^{k-2}+x^{k-3}+...+x^2+x)-1$

$=x^k-1$

You can also prove it by reversing the solution above.

$\endgroup$
  • $\begingroup$ May be (might be wrong) I want to view the identity as something, that changes polynomial, which in turn has components which can be removed (as in division), or multiplied. $\endgroup$ – jitender Feb 19 '18 at 16:39

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