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}

Advertisements