Question

This one is probably a bit interesting:

Suppose \(K\) be the number of integers n such that \( \frac{2^n+1}{n^2}\) is also an integer.Find \( K\).

Answer 1

2^(?)

Answer 2

write a python script!

Answer 3

\( \large \frac{2^n+1}{n^2} \)

Answer 4

for i in [1..infinity] if i 2^n+1/n**2 is an integer: k +=1

Answer 5

for n*

Answer 6

n must be odd

Answer 7

since 2^n + 1 is odd

Answer 8

no kidding guys, python isn't an option.

Answer 9

\[2^n + 1 = (2+1)(2^{n-1}-2^{n-2}...-2+1)\]

Answer 10

Please note this seems to be a hard problem, I only have the the answer, but no concrete proof (yet) or solution.

Answer 11

So it is finite?

Answer 12

I /knew/ it had to be hard as you didn't start it off as "An easy one..." - which are usually quite hard when you set them :-)

Answer 13

lol, yes it is finite of-course.

Answer 14

is it the fibonacci sequence?

Answer 15

asnaseer, you seem be stalking me :D haha

Answer 16

@agdg that would be infinite

Answer 17

:) - you set interesting and challenging questions - thats why

Answer 18

OK - I'm off to work on this one and, as Arnie would say, I'll be back!

Answer 19

does the answer have anything to do with the fibonacci sequence?

Answer 20

@asnaseer: I told about those 150 right? well the number just moved to 200 so things will get much interesting in the next few weeks ;)

Answer 21

FFM - can you please clarify the question - you say K is the NUMBER of integers n such that...
did you mean K represents a set of integers n such that?
i.e. is K the count of integers or the set of integers satisfying the condition?

Answer 22

I think the answer is 2 but have no idea how to prove it, that makes it just a guess

Answer 23

(2^2+1)/2^2 = 5/4 which is not an integer

Answer 24

K is the number of n that satisfies the given condition.

Answer 25

1and 3 does

Answer 26

n =1 and n = 3 works

Answer 27

yes why others won't work ?

Answer 28

I found 2 !

Answer 29

the answer is K = 2

Answer 30

but you must show why all the other numbers smaller or bigger than those 2 don't work

Answer 31

we need to prove there is no other solution from negative infinity to positive infinity - correct?

Answer 32

non-positive n is all non-integer

Answer 33

or am I mistaken?

Answer 34

are integers considered to be just the positive numbers?

Answer 35

I think I got a lead, let me work on a bit.

Answer 36

yes positive only, I think.

Answer 37

try plotting the graph for negative integers

Answer 38

so far I only got K = 2 :(

Answer 39

I'm thinking more of the definition of integers - I was always under the impression they were all negative and positive whole numbers

Answer 40

it only works for 1 and 3 :-D

Answer 41

we have to prove that \( 2^n+1 \gt n^2 \forall n >3 \)

Answer 42

that's plain induction routine I suppose ;)

Answer 43

wow

Answer 44

alright problem solved give us the next one!

Answer 45

I don't get it, how does that prove that \(2^n+1\) is not divisible by \(n^2\)?

Answer 46

No this is not what you need to prove. Just saying that it is bigger is not enough. It is a divisiblity problem

Answer 47

it is trivial that is bigger but how do you show taht 2^12589 +1 /12589^2 is not an integer?

Answer 48

I am really getting slow :P thanks asnaseer :)

Answer 49

just show that 12589^2 is even

Answer 50

:) true

Answer 51

turns out it is odd :-P what do we do now

Answer 52

I think I have a lead...

Answer 53

oh show that n^2 is not a factor of 2^n + 1

Answer 54

in one of your previous problems ( http://openstudy.com/users/foolformath#/updates/4f0305f8e4b01ad20b546de4) I proved that \(2^{2k+1}+1\) is always a multiple of 3. I wonder if that can be used here?

Answer 55

since here we know n must be odd we can say \(n=2k+1\)

Answer 56

but, n can be odd or even

Answer 57

no n must be odd

Answer 58

\(2^n+1\) is always odd isn't it?

Answer 59

yes.

Answer 60

therefore \(n^2\) must be odd

Answer 61

therefore n must be odd?

Answer 62

nope

Answer 63

yes

Answer 64

aha, right.

Answer 65

yes?

Answer 66

:)

Answer 67

only odd^anything is odd

Answer 68

2^n + 1 can be expanded as (2 + 1)(2^{n-1} - 2^{n-2} + 2^{n-3}... -2 +1)

Answer 69

2^n + 1 is always a multiple of 3

Answer 70

oh
so you reduced the domain of n to the odd numbers

Answer 71

so reduce it to 2 numbers!

Answer 72

what is the upper bound of the equation

Answer 73

so, so we have:\[\frac{2^n+1}{n^2}=\frac{2^{2k+1}+1}{(2k+1)^2}=\frac{3m}{(2k+1)^2}\]

Answer 74

yep!

Answer 75

?

Answer 76

agdgdgdgwngo - I had proved that \(2^{2k+1}=3m\) in an earlier post by FFM

Answer 77

so 2^2k+1 is a multiple of 3?

Answer 78

yes - you can prove it using induction

Answer 79

so you're close to proving that K = 2

Answer 80

It can be expanded as
(2 + 1)(2^{n-1} - 2^{n-2} + 2^{n-3}... -2 +1).
when n is odd

Answer 81

There is one liner proof that \( 2^n+1\) is a multiple of 3 when n is odd.

Answer 82

but that uses some number theory notation

Answer 83

ok - we know the original numerator \(2^n+1\) is odd, therefore 3m must be odd, therefore m must be odd, so now we have:\[\frac{2^n+1}{n^2}=\frac{2^{2k+1}+1}{(2k+1)^2}=\frac{3m}{(2k+1)^2}=\frac{3(2j+1)}{(2k+1)^2}\]where \(m=2j+1\)

Answer 84

aha

Answer 85

you got it ?

Answer 86

this must imply 2j+1 must be divisible by 2k+1 - right?

Answer 87

therefore only solutions are when j=k

Answer 88

which leaves:\[\frac{3}{2k+1}\]

Answer 89

and that only has a solution for k=0 and k=1

Answer 90

bingo!

Answer 91

but I found k = 2

Answer 92

nice

Answer 93

K=2 - I have little k here :-)

Answer 94

or do you mean that the 2 numbers are 1 and 3

Answer 95

oh... symbol overload

Answer 96

lol!

Answer 97

my python solution came up with K = 2 for n = 1 and 3 in half a second..... how long did this take? an hour.

Answer 98

that felt really satisfying - time to go eat now - thx FFM for setting such wonderful problems - I feel young again! :-)