Diminished Radix Complement (geometric pattern)

Apr 2015
2
0
Raleigh, NC
So I'm reading about Radix Complements on Wikipedia, and there is a geometric pattern used to prove the following statement:
The radix complement is most easily obtained by adding 1 to the diminished radix complement, which is (bn-1)-y. Since bn-1 is the digit b-1 repeated n times because
bn-1 = bn-1n = (b-1)(bn-1+bn-2...+b+1) = (b-1)bn-1+ (b-1)bn-2 +...+b-1

I'm trying to understand the third step in this pattern. I understand that an intermediary step would be (b-1)n but why does this translate into (b-1)(bn-1+bn-2...+b+1)?

Thanks,
deersfeet
 
Dec 2013
2,002
757
Colombia
Try expanding the brackets in the third step. You should get back to the second step (with no intermediates).
 
Jun 2008
149
28
Uppsala, Sweden
I'm trying to understand the third step in this pattern. I understand that an intermediary step would be (b-1)n but why does this translate into (b-1)(bn-1+bn-2...+b+1)?
You are getting confused between two things here
First establish the following
1. Using the binomial expansion \(\displaystyle (b-1)^n = \sum^n_{i=0} (-1)^n C^n_i b^{n-i}\), so \(\displaystyle b^n-1^n \neq (b-1)^n\), where \(\displaystyle C^n_i = \frac{n!}{(n-i)!. i!}\).


2.Say \(\displaystyle S_n = b^{n-1}+b^{n-2}+....b^2+b+1\) (Eq 1)

\(\displaystyle b.S_n = b^{n}+b^{n-1}+....b^2+b\) (Eq 2)

Subtracting (Eq 1) from (Eq 2) we have

\(\displaystyle b.S_n - S_n= b^{n}-1 \implies (b-1)S_n = b^n-1\) as already stated.

Hope this helped.
~Kalyan.
 
Apr 2015
2
0
Raleigh, NC
Hi Kalyan,
Thanks for responding! Your final answer makes some sense to me but I don't understand some of the notation. What do b.Sn and (n-1)!.i! mean?
 
Jun 2008
149
28
Uppsala, Sweden
What do b.Sn and (n-1)!.i! mean?
\(\displaystyle b.S_n\) means \(\displaystyle S_n\) is multiplied by \(\displaystyle b\) and \(\displaystyle n!\) is read as "n factorial" for some positive integer \(\displaystyle n\).

You may look into binomial theorem and summation of geometric series to have a better understanding into this. Hope it helps.

~K
 
Similar Math Discussions Math Forum Date
Number Theory