Hey I was having a little trouble with this one problem and was wondering if you all could help me.

I have to explain why:

2 ^(k-1)(2 ^(k)-1) is perfect if 2 ^(k)-1 is prime.

Any ideas on how I would start this?

Printable View

- Oct 19th 2008, 08:33 AMBlakeRobertsonMDPerfect Numbers
Hey I was having a little trouble with this one problem and was wondering if you all could help me.

I have to explain why:

2 ^(k-1)(2 ^(k)-1) is perfect if 2 ^(k)-1 is prime.

Any ideas on how I would start this? - Oct 19th 2008, 08:40 AMThePerfectHacker
Let $\displaystyle \sigma (n)$ be the sum of divisors of $\displaystyle n$.

It is easy to show $\displaystyle \sigma (2^r) = 2^{r+1} - 1$.

Also $\displaystyle \sigma (p) = p+1$ if $\displaystyle p$ is prime.

Finally $\displaystyle \sigma (ab) = \sigma (a ) \sigma (b)$ if $\displaystyle \gcd(a,b)=1$.

A number of perfect if and only if $\displaystyle \sigma (n) = 2n$.

Set $\displaystyle n=2^{k-1} (2^k -1)$ and use the above results. - Oct 19th 2008, 09:54 AMBlakeRobertsonMD
Thanks. I written up a proof of induction and I think I got the problem to work well. Can any of you tell me if this sounds about correct?

Proof: 2 ^ (k – 1) ( 2 ^ k – 1) is always perfect when 2 ^ k - 1 is prime.

We will use induction for this proof.

Let P(k) be the predicate: 2^(k-1) (2 ^(k) -1).

Base Case: Let P(2).

2^(2-1) (2 ^ (2) -1) = 2 * 3 = 6

As you see k = 2 lets 2 ^ k – 1 become 3 which is the lowest prime number possible for this equation.

Our answer to the equation is 6 which is a perfect number because:

6 = 1 + 2 + 3.

Inductive Step: Assume that P(k) is true, where k >= 2. Then P(k + 1) is also true, because:

Using assumption we add (k+1) to the equation:

2 ^ ((k+1)-1) * (2 ^ (k+1) – 1)

As the equation shows P(k) implies P(k+1) for every natural number k >=2.

By Principle of induction, 2^(k – 1)(2^(k)-1) is a perfect number if 2^(k) -1 is a prime number for every natural number k>=2, which proves the claim.

How does it sound? - Oct 19th 2008, 10:10 AMo_O
That doesn't work. The statement doesn't say that it works for every k greater than or equal to 2. For example, take k = 6. $\displaystyle 2^{6} - 1 = 63$ which isn't prime. I don't quite see how you got your inductive step to work. It seems you just said 'P(k) implies P(k+1)' without actually showing it.

Use the hints ThePerfectHacker gave you.

$\displaystyle \begin{array}{rcll}\sigma (n) & = & \sigma \! \bigg(2^{k-1} \left(2^k - 1\right) \bigg) & \\ & = & \sigma (2^{k-1}) \cdot \sigma (2^k - 1) & \quad \text{Since: } \text{gcd}\!\left(2^{k}-1, 2^{k-1}\right) = 1 \\ & = & (2^k - 1) \cdot 2^k & \quad \text{Since: } \sigma (2^r) = 2^{r+1} - 1 \ \text{and} \ \sigma (p) = p + 1 \\ & \vdots & & \end{array} $ - Oct 19th 2008, 10:12 AMBlakeRobertsonMD
So is n just any natural number or what? Not really sure where n came from.

Also I made a mistake in the first posting, 2^(k) -1 is prime, not 2^(k-1). sorry >< - Oct 19th 2008, 10:13 AMo_O
No. As TPH gave you, $\displaystyle n = 2^{k-1} \left(2^k - 1\right)$.

We have to prove that $\displaystyle \sigma (n) = 2n$ since this is what it means for $\displaystyle n$ to be perfect. Read through TPH's hints then the post I gave. - Oct 19th 2008, 10:41 AMBlakeRobertsonMD
Okay personally I'm lost. I was never good at discrete math and I was never really good at induction either.

I've never used the divisor function nor was I ever taught it. Usually I would think that the sum of all the divisors of a number would equal the number if it was truely perfect, not 2 * the number as shown with 2n.

Sorry but after the hints you and the perfect hacker gave me, i'm still lost. Such as how did you go from o(2^(k-1)) * o(2^(k) - 1) to just 2^(k) -1 * 2 ^(k).

I'm sorry if I seem slow with this. - Oct 19th 2008, 11:01 AMo_O
A number exist iff it is equal to the sum of its positive divisors excluding itself, i.e. $\displaystyle \underbrace{\sigma (n)}_{\text{the sum of its divisors}} - \underbrace{n}_{\text{excluding itself}} = n$.

Simply moving n to the other side gives us $\displaystyle \sigma (n) = 2n$. So if n is perfect, then $\displaystyle \sigma (n) = 2n$

To answer your questions:

**1.**Why $\displaystyle \sigma (2^{k-1}) = 2^k - 1$.

What are the divisors of $\displaystyle 2^r$? Well, there's $\displaystyle 1, 2, 2^2, 2^3, \hdots, 2^{r-1}, 2^r$. For example, $\displaystyle 2^8$ can be divided by 1, 2, 4, 8, etc. since $\displaystyle \frac{2^8}{2^2} = 2^6, \ \frac{2^8}{2^3} = 2^5, \ \hdots$

Now, TPH said that the sum of the divisors of $\displaystyle 2^r$ is $\displaystyle 2^{r+1} - 1$. In other words: $\displaystyle 1 + 2 + 2^2 + \hdots + 2^r = 2^{r+1} - 1$

To prove this, let $\displaystyle S = 1 + 2 + 2^2 + \hdots + 2^r$ and then consider $\displaystyle S = 2S - S$ and you will get the desired result.

Thus, $\displaystyle \sigma(2^r) = 1 + 2 + 2^2 + \hdots + 2^{r-1} + 2^r = 2^{r+1} - 1$. Now imagine $\displaystyle r = k-1$ and you're set.

__________________________________________________ ____________________________________

**2.**Why does $\displaystyle \sigma (2^k - 1) = 2^k$ ?

We were given that $\displaystyle 2^k - 1$ is**prime**. For any prime, its divisors are 1 and itself. So, the sum of its divisors is just itself plus 1, i.e. $\displaystyle \sigma (p) = p + 1$ where $\displaystyle p$ is prime.

Now put (1) and (2) together and you get what you needed. - Oct 19th 2008, 01:33 PMBlakeRobertsonMD
Okay so the overall equation is 2^(2k)-(2^(k))

- Oct 19th 2008, 03:00 PMo_O
No. Should be $\displaystyle 2^{k+1} - 2^k$. But that isn't the way to go.

Factor out a 2 from $\displaystyle 2^k$ and you should notice that: $\displaystyle 2^{k} \left( 2^{k} - 1\right) = 2^1 \cdot \underbrace{ 2^{k-1}\left( 2^{k} - 1\right)}_{n} = 2n$