Problem 4 - Perfect Squares

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Problem 4 - Perfect Squares

G H J

Reveal topic tags

Perfect Squares

L

G H BBookmark kLocked kLocked NReply

Source: 2020 Austrian National Competition for Advanced Students, Part 1 problem 4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

Ln142

#1 h Jun 6, 2020, 1:13 PM

Y by

Determine all positive integers $N$ such that
$2^N-2N$ is a perfect square.

(Walther Janous)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

257 posts

#2 h Jun 6, 2020, 2:49 PM • 1 Y

Y by pavel kozlov

if $N=1(mod 2)$ and $N\ge 3$
then $2^N-2N=2(mod 4)$ is not a perfect square.
if $N=0(mod 2)$ and $N\ge 8$ ,assume that $N=2k$ ,
then $(2^k-1)^2<2^N-2N=2^{2k}-4k<(2^k)^2$ is not a perfect square.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

Ln142

#3 h Jun 6, 2020, 2:53 PM

Y by

yefangzhou wrote:

if $N=1(mod 2)$ and $N\ge 3$
then $2^N-2N=2(mod 4)$ is not a perfect square.
if $N=0(mod 2)$ and $N\ge 8$ ,assume that $N=2k$ ,
then $(2^k-1)^2<2^N-2N=2^{2k}-4k<(2^k)^2$ is not a perfect square.

How would you prove $\left({2^k-1}\right)^2 < 2^{2k}-4k$ ? I used an induction proof at the competition.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

257 posts

#4 h Jun 6, 2020, 3:01 PM

Y by

derivative could help.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

Ln142

#5 h Jun 6, 2020, 3:23 PM

Y by

I proved it in this manner:
$\left({2^k-1}\right)^2 < 2^{2k}-4k$ is equivalent to $2^{k+1} > 4k+1$

Base:
$k=3$
$16 > 13$

Induction hypothesis:
$2^{k+1} > 4k+1$ for all positive integers $k \leq 3$

Inductive step:
We have to show:
$2^{k+2} > 4k+5$

From the induction hypothesis we know:
$2^{k+2} >8k+2$

If we can show:
$8k+2 > 4k +5$ then $2^{k+2} > 4k+5$ must also be true.

This is equal to $k> 3/4$ which is obviously true for $k \geq 3$
Thus, the equation $2^{k+1} > 4k+1$ must be true for $k \geq 3$

Checking the remaining even cases yields the solution 0 for $N=2$ , checking the case $N=1$ yields the solution 1. (the case $N=1$ has to be cheked because $2^N-2N$ is not an even number for $N=1$ )

Thus $N=1$ and $N=2$ are the only solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

804 posts

#6 h Jun 6, 2020, 5:16 PM

Y by

@above maybe this is more common: Let $P(k): 2^{k+1}>4k+1: k\ge 3$ . Easily $P (3)$ works so assume $P(k)$ works for some $k\ge 3$ .
$P^{-1}(k+1):4(k+1)+1=(4k+1)+4<2^{k+1}+4 <2^{k+1}+2^{k+1}=2^{k+2}$

So $P (k+1)$ is true and the induction on $P$ holds

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a