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?
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?
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. 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.
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.
A number exist iff it is equal to the sum of its positive divisors excluding itself, i.e. .
Simply moving n to the other side gives us . So if n is perfect, then
To answer your questions:
1. Why .
What are the divisors of ? Well, there's . For example, can be divided by 1, 2, 4, 8, etc. since
Now, TPH said that the sum of the divisors of is . In other words:
To prove this, let and then consider and you will get the desired result.
Thus, . Now imagine and you're set.
2. Why does ?
We were given that is prime. For any prime, its divisors are 1 and itself. So, the sum of its divisors is just itself plus 1, i.e. where is prime.
Now put (1) and (2) together and you get what you needed.