Search

themathematic

Derive (xⁿ – 1) with base number system

Lets derive,

(x^n - 1) = (x - 1)(x^{n-1} + x^{n-2} + ... + x^2 + x + 1)

One way to prove the above equality is to use summation of geometric progression which goes as follows,

\begin{aligned} \sum_{n=0}^{n - 1} {x^a} = \frac{(x^n - 1)}{(x - 1)} \end{aligned} \  \ \forall \  x \neq 0

My intention is to get (xⁿ – 1) from scratch with a unique way, by changing base of natural numbers and exploiting their ease of usage.

The number system we generally use is base 10, ie., using a permutation of 10 different digits from 0 to 9 and their known place values. But base 2 numbers use 2 digits only ie., 0 and 1. Further we can generate any base number system. I will represent base 2 number as 11_{(2)}, 1101_{(2)} , base 10 numbers as 23, 110 and generally base (n + 1) numbers as nnn..(a \ times)_{(n + 1)}

In base 2 number system following observation can be done,
(I feel the below conclusion is obvious for some readers)

\begin{aligned} & 10_{(2)} - 1  & = & 1_{(2)} & \implies & 2 - 1 & = 2^1 - 1 \\ & 100_{(2)} - 1 & = & 11_{(2)} & \implies & 4 - 1 & = 2^2 - 1 \\ & 1000_{(2)} - 1 & = & 111_{(2)} & \implies & 8-1 & = 2^3 - 1 \\ & 100...0_{(2)} - 1 & = & 111...1_{(2)} & \implies & 111...1_{(2)} & = 2^n - 1 \\ \end{aligned}

Lets consider the case of n digit base 2 number,

\begin{aligned} & (2^n - 1) &&{} = 1111...1_{(2)}  \rightarrow \ n \ digits \end{aligned}\\ \begin{aligned} & (2^n - 1) &&{} = & 2^{(n-1)} & + 2^{(n-2)} & + \ ... \ & + 2^2 & + 2 & + 1 \\ & \  &&{} = 1 & (2^{(n-1)} & + 2^{(n-2)} & + \ ... \ & + 2^2 & + 2 & + 1) \\ & \  &&{} = (2 - 1) & (2^{(n-1)} & + 2^{(n-2)} & + \ ... \ & + 2^2 & + 2 & + 1) \\ \end{aligned}

Hence, equation for (x^n - 1) is shown for x = 2. Lets consider n digit base 3 number,

\begin{aligned} & (3^n - 1) &&{} = 2222...2_{(3)}  \rightarrow \ n \ digits \end{aligned}\\ \begin{aligned} & (3^n - 1) &&{} = & 2.3^{(n-1)} & + 2.3^{(n-2)} & + \ ... \ & + 2.3^2 & + & 2.3 & + & 2 \\ & \  &&{} = 2 & (3^{(n-1)} & + 3^{(n-2)} & + \ ... \ & + 3^2 & + & 3 & + & 1) \\ & \  &&{} = (3 - 1) & (3^{(n-1)} & + 3^{(n-2)} & + \ ... \ & + 3^2 & + & 3 & + & 1) \\ \end{aligned}

Hence, equation for (x^n - 1) is shown for x = 3. Lets consider n digit base x number,

\begin{aligned} & (x^n - 1) &&{} = & (x-1)(x-1)(x-1)...(x-1)_{(x)}  \rightarrow \ n \ digits \end{aligned}\\ \begin{aligned} & (x^n - 1) &&{} = (x-1)x^{(n-1)} &&{} + (x-1)x^{(n-2)} &&{} + \ ... \  + (x-1)x^2 &&{} + (x-1)x &&{} + (x-1).1 \\ & \  &&{} = (x-1) (x^{(n-1)} &&{} + x^{(n-2)} &&{} + \ ... \  + x^2 &&{} + x &&{} + 1) \end{aligned}

Hence,
\begin{aligned} (x^n - 1) = (x - 1)(x^{(n-1)} + x^{(n-2)} +\  ... \ + x^2 + x + 1) \\ \end{aligned}

Sum of 1 to n, n² or n³

We will derive summation of series with increasing difficulty.

Lets derive the simplest series summation formulas,

\begin{aligned} \sum_{n=1}^{n} {x} = 1 + 2 + 3 + ... + (n-2) + (n-1) + n \end{aligned}

To derive a formula to this series consider adding the same series with all numbers reversed, that is n + (n-1) + (n-2) and so on till 3 + 2 + 1 i.e, check the following equations,

\begin{aligned} & \sum_{n=1}^{n} {x} &&{} = 1 && + 2 && + 3 && + ... && + (n-2) && + (n-1) && + n \\ & \sum_{n=1}^{n} {x} &&{} = n && + (n-1) && + (n-2) && + ... && + 3 && + 2 && + 1 \\ \hline 2 . & \sum_{n=1}^{n} {x} &&{} = (n+1) && + (n+1) && + (n+1) && + ... && + (n+1) && + (n+1) && + (n+1) \end{aligned}

Simplifying, we get

\begin{aligned} 2 . & \sum_{x=1}^{n} {x} &&{} = (n+1) + (n+1) + ... \  n \  times \\ 2 . & \sum_{x=1}^{n}{x} &&{} = n(n+1) \\ & \sum_{x=1}^{n}{x} &&{} = \frac {n(n+1)}{2} \end{aligned}

Well that’s a simple series how about sum of squares! before that we will understand simple properties of \sum symbol.

\begin{aligned} & \sum_{x=1}^{n} (x + 1) &&{} = \sum_{x=1}^{n} x + \sum_{x=1}^{n} 1 = n + \sum_{x=1}^{n} x \\ & \sum_{x=1}^{n} (x + f(x)) &&{} = \sum_{x=1}^{n} x + \sum_{x=1}^{n} f(x) \\ & \sum_{x=1}^{n} (4 + x + 2x^2) &&{} = 4n + \sum_{x=1}^{n} x + 2. \sum_{x=1}^{n} x^2 \end{aligned}

If we observe the formula \sum_{x=1}^{n}{x} = \frac {n(n+1)}{2} , the summation of x is having terms of x^2 and x alone, so if we do \sum \Big( \sum x \Big) we will end up in equation with terms \sum x^2 which can be kept on one side and rest of the terms will be either algebraic function of n or \sum x only.

Lets define a series called S so that,

\begin{aligned} S =& 1 + (1 + 2) + (1 + 2 + 3) + ... + (1 + 2 + 3 + ... + 4) \\ S =& 1.n + 2(n-1) + 3(n-2) + ... + p(n - p + 1) + (p + 1)(n - p) + ... + (n - 1)(n - n + 2) + n(n - n + 1) \\ S =& n + 2n + 3n + ... + pn + (p + 1)n + ... + (n - 1)n + n.n \\ &- [1.0 + 2.1 + 3.2 + ... + p(p - 1) + (p + 1)p + ... + (n - 1)(n - 2) + n(n - 1)] \\ S =& n \sum_{x=1}^{n}{x} - \sum_{x=1}^{n}{x(x - 1)} \end{aligned}

Also the series S expands as follows,

\begin{aligned} S =& \sum_{x=1}^{n} {\Big (\sum_{y=1}^{x} {y} \Big)} =& \frac{1}{2} \sum_{x=1}^{n} {(x^2 + x)} \end{aligned}

Now using above two equations of summation S, we have

\begin{aligned} \frac{1}{2} \sum_{x=1}^{n} {(x^2 + x)} =& n \sum_{x=1}^{n}{x} - \sum_{x=1}^{n}{x(x - 1)} \\ \frac{3}{2} \sum_{x=1}^{n} {x^2} =& \frac{2n + 1}{2} \sum_{x=1}^{n} {x} \\ =& (2n + 1)\frac{n(n + 1)}{4} \\ \sum_{x=1}^{n} {x^2} =& \frac{n(n + 1)(2n + 1)}{6} \end{aligned}

By using this we can now solve sum of series like \sum_{x=1}^{n} (4 + x + 2x^2) mentioned in the above example. Further we can continue with the same technique to get sum of cubic numbers,

\begin{aligned} S =& 1^2 + (1^2 + 2^2) + (1^2 + 2^2 + 3^2) + ... + (1^2 + 2^2 + 3^2 + ... + 4^2) \\ S =& 1^2.n + 2^2(n-1) + 3^2(n-2) + ... + p^2(n - p + 1) + (p + 1)^2(n - p) + ... + (n - 1)^2(n - n + 2) + n^2(n - n + 1) \\ S =& n + 2^2n + 3^2n + ... + p^2n + (p + 1)^2n + ... + (n - 1)^2n + n^2.n \\ &- [1^2.0 + 2^2.1 + 3^2.2 + ... + p^2(p - 1) + (p + 1)^2p + ... + (n - 1)^2(n - 2) + n^2(n - 1)] \\ S =& n \sum_{x=1}^{n}{x^2} - \sum_{x=1}^{n}{x^2(x - 1)} \\ S =& n \sum_{x=1}^{n}{x^2} - \sum_{x=1}^{n}{(x^3 - x^2)} \\ S =& (n + 1) \sum_{x=1}^{n}{x^2} - \sum_{x=1}^{n}{x^3} \end{aligned}

Also the series S expands as follows,

\begin{aligned} S &= \sum_{x=1}^{n} {\Big (\sum_{y=1}^{x} {y^2} \Big)} \\ &= \frac{1}{6} \sum_{x=1}^{n} {x(x + 1)(2x + 1)} \\ &= \frac{1}{6} \sum_{x=1}^{n} {(2x^3 + 3x^2 + x)} \end{aligned}

Now using above two equations of summation S, we have

\begin{aligned} (n + 1) \sum_{x=1}^{n}{x^2} - \sum_{x=1}^{n}{x^3} &= \frac{1}{6} \sum_{x=1}^{n} {(2x^3 + 3x^2 + x)} \\ \sum_{x=1}^{n} {(2x^3 + 3x^2 + x)} &= 6(n + 1) \sum_{x=1}^{n}{x^2} - 6\sum_{x=1}^{n}{x^3} \\ \sum_{x=1}^{n} {(2x^3 + 6x^3)} &= \sum_{x=1}^{n}{(6(n + 1)x^2 - 3x^2)} - \sum_{x=1}^{n}{x} \\ \sum_{x=1}^{n} {8x^3} &= (6n + 3)\sum_{x=1}^{n}{x^2} - \sum_{x=1}^{n}{x} \\ \sum_{x=1}^{n} {8x^3} &= 3(2n + 1)\frac{n(n + 1)(2n + 1)}{6} - \frac{n(n + 1)}{2} \\ \sum_{x=1}^{n} {x^3} &= \frac{n(n + 1)(2n + 1)^2}{2.8} - \frac{n(n + 1)}{2.8} \\ \sum_{x=1}^{n} {x^3} &= \frac{n(n + 1)(2n + 1)^2 - n(n + 1)}{16} \\ \sum_{x=1}^{n} {x^3} &= \frac{n(n + 1)((2n + 1)^2 - 1)}{16} \\ \sum_{x=1}^{n} {x^3} &= \frac{n(n + 1)(4n^2 + 4n)}{16} \\ \sum_{x=1}^{n} {x^3} &= \frac{n(n + 1)(4n)(n + 1)}{16} \\ \sum_{x=1}^{n} {x^3} &= \frac{n^2(n + 1)^2}{4} \end{aligned}

Hope you will go further to derive higher order formula and who knows a general solution!

Create a free website or blog at WordPress.com.

Up ↑