Bosnia and Herzegovina 2022 IMO TST P3

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

Bosnia and Herzegovina 2022 IMO TST P3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

618 posts

#1 h May 22, 2022, 6:53 AM • 4 Y

Y by amar_04, Mango247, Mango247, Mango247

An infinite sequence is given by $x_1=2, x_2=7, x_{n+1} = 4x_n - x_{n-1}$ for all $n \geq 2$ . Does there exist a perfect square in this sequence?
Remark

This post has been edited 1 time. Last edited by Steve12345, May 22, 2022, 7:12 AM

Z K Y

The post below has been deleted. Click to close.

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

1385 posts

#2 h May 22, 2022, 8:29 AM

Y by

Sketch

This post has been edited 1 time. Last edited by VicKmath7, May 22, 2022, 8:30 AM

Z K Y

The post below has been deleted. Click to close.

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

1915 posts

#3 h May 22, 2022, 11:50 AM

Y by

I will just derive the closed form. We proceed to find the general closed form by taking the GF (Generating function) of the sequence $\{x_n\}$ , I'll label $a_0=2$ , $a_1=7$ as the seed values. Denote $A(x)=\sum_{n=0}^{\infty}a_nx^n$ as the GF of $\{a_n\}$ . Then,
$\begin{align*} A(x)=\sum_{n=0}^{\infty}a_nx^n &=2+7x+\sum_{n=2}a_nx^n\\ &=2+7x+x\left(\sum_{n=1}^{\infty}a_{n+1}x^n\right)\\ &=2+7x+x\left(\sum_{n=1}^{\infty}(4a_n-a_{n-1})x^n\right)\\ &=2+7x+x\left(4\sum_{n=1}^{\infty}a_nx^n-x\sum_{n=0}^{\infty}a_nx^n\right)\\ &=2+7x+x\left(4(A(x)-2)-xA(x)\right)\\ &\implies A(x)=\frac{2-x}{x^2-4x+1} \end{align*}$
So, the GF of $\{a_n\}$ is $\frac{2-x}{x^2-4x+1}$ , next let $r_1:=2+\sqrt 3$ and $r_2=2-\sqrt{3}$ denote the reals roots of $x^2-4x+1$ , with this we can write $A(x)$ as follows,
$A(x)=-\frac{1}{2}\left(\frac{(x-r_1)+(x-r_2)}{(x-r_1)(x-r_2)}\right)=\frac{1}{2}\left(\frac{1}{r_1-x}+\frac{1}{r_2-x}\right)=\frac{1}{2}\left(\frac{\frac{1}{r_1}}{1-\frac{x}{r_1}}+\frac{\frac{1}{r_2}}{1-\frac{x}{r_2}}\right)$ Now using properties of geometric series we can expand out $A(x)$ as $A(x)=\sum_{n=0}^{\infty}\frac{1}{2}\left(\frac{1}{r_1^{n+1}}+\frac{1}{r_2^{n+1}}\right)x^n$ But by Vieta's relations $r_1r_2=1$ , thus, $\frac{1}{2}\left(\frac{1}{r_1^{n+1}}+\frac{1}{r_2^{n+1}}\right)=\frac{r_1^{n+1}+r_2^{n+1}}{2}$ , thus $A(x)=\sum_{n=0}^{\infty}a_nx^n=\left(\frac{(2+\sqrt{3})^{n+1}+(2-\sqrt{3})^{n+1}}{2}\right)x^n\implies\boxed{x_n=\frac{(2+\sqrt{3})^n+(2-\sqrt{3})^n}{2}}\qquad\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

113 posts

#4 h May 23, 2022, 10:38 PM

Y by

amar_04 wrote:

I will just derive the closed form. We proceed to find the general closed form by taking the GF (Generating function) of the sequence $\{x_n\}$ , I'll label $a_0=2$ , $a_1=7$ as the seed values. Denote $A(x)=\sum_{n=0}^{\infty}a_nx^n$ as the GF of $\{a_n\}$ . Then,
$\begin{align*} A(x)=\sum_{n=0}^{\infty}a_nx^n &=2+7x+\sum_{n=2}a_nx^n\\ &=2+7x+x\left(\sum_{n=1}^{\infty}a_{n+1}x^n\right)\\ &=2+7x+x\left(\sum_{n=1}^{\infty}(4a_n-a_{n-1})x^n\right)\\ &=2+7x+x\left(4\sum_{n=1}^{\infty}a_nx^n-x\sum_{n=0}^{\infty}a_nx^n\right)\\ &=2+7x+x\left(4(A(x)-2)-xA(x)\right)\\ &\implies A(x)=\frac{2-x}{x^2-4x+1} \end{align*}$
So, the GF of $\{a_n\}$ is $\frac{2-x}{x^2-4x+1}$ , next let $r_1:=2+\sqrt 3$ and $r_2=2-\sqrt{3}$ denote the reals roots of $x^2-4x+1$ , with this we can write $A(x)$ as follows,
$A(x)=-\frac{1}{2}\left(\frac{(x-r_1)+(x-r_2)}{(x-r_1)(x-r_2)}\right)=\frac{1}{2}\left(\frac{1}{r_1-x}+\frac{1}{r_2-x}\right)=\frac{1}{2}\left(\frac{\frac{1}{r_1}}{1-\frac{x}{r_1}}+\frac{\frac{1}{r_2}}{1-\frac{x}{r_2}}\right)$ Now using properties of geometric series we can expand out $A(x)$ as $A(x)=\sum_{n=0}^{\infty}\frac{1}{2}\left(\frac{1}{r_1^{n+1}}+\frac{1}{r_2^{n+1}}\right)x^n$ But by Vieta's relations $r_1r_2=1$ , thus, $\frac{1}{2}\left(\frac{1}{r_1^{n+1}}+\frac{1}{r_2^{n+1}}\right)=\frac{r_1^{n+1}+r_2^{n+1}}{2}$ , thus $A(x)=\sum_{n=0}^{\infty}a_nx^n=\left(\frac{(2+\sqrt{3})^{n+1}+(2-\sqrt{3})^{n+1}}{2}\right)x^n\implies\boxed{x_n=\frac{(2+\sqrt{3})^n+(2-\sqrt{3})^n}{2}}\qquad\blacksquare$

How would you finish the problem after deriving the closed form?

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a