Question

\(\large (X)_{i=1}^{\infty} : X _{1} = 1 , X _{2} = 1 ~ , X _{n+1} = X _{n} + 2X _{n-1} \hspace{15px} n \ge 2\)

\( \large (Y)_{i=1}^{\infty} : Y _{1} = 1 , Y _{2} = 7 ~ , Y _{n+1} = 2Y _{n} + 3Y _{n-1} \hspace{15px} n \ge 2 \)

Prove that none of the terms in those sequences is common (except the first one which is 1)

Answer 1

ok so X and Y are sequence right ?

Answer 2

yes

Answer 3

any by Prove that none of the members in those sequences is common (except the first one which is 1) u mean
show that
\(X_j\neq Yi ~~~~~~\forall i,j\in N\)

Answer 4

exactly,and i have got some ideas (i think), write the members , u will discover sth nice about the sequence X ... but for Y i havn't got any...

Answer 5

ok , i'll see what i got :D

Answer 6

interesting xD so you want to show that the both sequences have no common terms except 1

Answer 7

yes

Answer 8

the funny thing i have found is that \( X _{n} = 2X _{n-1} + (-1)^{n-1} \)

Answer 9

i'm looking for the same thing for the second seuqence

Answer 10

yep thats jacobsthal sequence

Answer 11

ermm

Answer 12

we can find \(X_{n} \) and \( Y_{n} \) by a way which is called generating function:
http://en.wikipedia.org/wiki/Generating_function
but i don't think it helps...

Answer 13

i don't know anything about that..

Answer 14

We have \[Y_n > X_n\text { for } n > 1\]

Answer 15

It is easy to prove this by induction. I know we want more than that.

Answer 16

I will think about it

Answer 17

but
\(X_6>Y_2\) so hmm

Answer 18

i think @eliassaab mean same members,for example \(X_{2} \) and \( Y_{2} \) or sth else

Answer 19

yeah i know misunderstanding of the question

Answer 20

according to
http://mathworld.wolfram.com/JacobsthalNumber.html

Answer 21

\(\Huge X_n=\sum _{r=0}^{\left \lfloor (n-1)/2 \right \rfloor} \binom{n-1-r}{r}2^r
\)

Answer 22

and for \(Y \) ?i don't think it does help...

Answer 23

so we reduced X_n so far to this
\(\large X_n=\frac{1}{3}[2^n-(-1)^n]~~~~~~\forall n\ge 2\)

Answer 24

think about it i'll be online soon.

Answer 25

k :D
btw u have an answer for this ?

Answer 26

the interesting thing i note about Y
that
\(Y_n \mod 10 =1,7,7,5 ~~~~~\text{(in pattern )}\)

Answer 27

and
\(X_n \mod 10 =1,1,3,5 ~~~~~\text{(in pattern )}\)

Answer 28

so lets assume \(n=4k+q\)
these cases that we might have common terms
\(n=4k\\n=4k+1\)

Answer 29

so for n=4k
lets assume we have some g,h such that
\(X_g=Y_h\) for some \(g=4i\) and \(h=4j\)

Answer 30

\(\large X_{g}=\frac{1}{3}[2^g-1]\\ ~~~~~~~~\large =\frac{1}{3}[2^{4i}-1]\\ ~~~~~~~~\large =5 \mod 10\\ \large Y_h=2Y_{h-1}+3Y_{h-2} \\ \large ~~~~~=2Y_{4j-1}+3Y_{4j-2}\\ \large ~~~~~ =2\times 7+3 \times 7(\mod 10)=5 \mod 10\)

Answer 31

ermm we only need a contradiction xD

Answer 32

ok i give up :P

Answer 33

Let's suppose by contradiction that exists an integer, say\[n _{0}>2\]
such that we have:
\[a _{n _{0}}=b _{n _{0}}\]
then we can write:
\[\frac{ b_{n _{0}+1}-b _{n _{0}-1} }{ 2 }=a _{n _{0}}+b _{n _{0}-1}\]
and:
\[a _{n _{0}+1}-a _{n _{0}-1}=a _{n _{0}}+a _{n _{0}-1}\]
so if we subtract side by side those above equation, we will get this:
\[\frac{ b _{n _{0}+1}-b _{n _{0}-1} }{ 2 }-(a _{n _{n}+1}-a _{n _{0}-1})=b _{n _{0}-1}-a _{n _{0}-1}\]
and after some simplification, I get this:
\[b _{n _{0}}=a _{n _{0}+1}\]
which is a contraddiction!

Answer 34

oops..I use a in place of X
and b in place of Y

Answer 35

hmm not sure , note that n need not to be the same for both terms other wise using induction as elissab said works .

Answer 36

Please, note that, setting a=b for n_0, I denied the thesis of the statement, and by my subsequent reasoning, I got an absurd statement

Answer 37

...so the statement of our question is true!

Answer 38

@Marki , ur idea was cool ;D , made sense to me ;)

Answer 39

i'm eager to see ur finished proof.

Answer 40

i can get the correct proof if u want...these questions are in my number theory book and i can get the answers for all of them (but i don't get and prefer to prove it my self)...

Answer 41

To me, generating function of X is \(X_n= \dfrac{1}{3}(2^n+(-1)^n)\) and generating function of Y is \(Y_n= \dfrac{1}{4}(3^n+(-1)^n)\)

Answer 42

Suppose there is at some value, \(X_n = Y_n\) and we get contradiction. But I didn't get that result yet :)

Answer 43

please, note that my solution is logically very consistent!

Answer 44

:) yes, sir @Michele_Laino

Answer 45

@Loser66 , yes @Marki tried to use generating function but no need to use that! in my book this question is supposed to be solved only bu modular properties.

Answer 46

Thank you very much! @Loser66

Answer 47

@loser OMG ! thank u for the Y function xD i was dying to know it !!!

Answer 48

@Marki , isn't it \( (-1)^i \) and j?

Answer 49

\(\large \text{assume there is i,j s.t}\\
\\
\large \begin{align*}
X_i& =Y_j~~~~~\text{for some }i,j\in N \\
\frac{1}{3}2^i+(-1)^i &= \frac{1}{4}3^j+(-1)^j \\
4(2^i+(-1)^i )&=3(3^j+(-1)^j) \\
(2^{i+2}+4(-1)^i ) &= (3^{j+1}+3(-1)^j)
\end{align*}\)

Answer 50

now last line does not give integer solutions i'll show why

Answer 51

@Marki , ur going very well,continue ;)

Answer 52

guys wait!!! a very very easy solution!

Answer 53

we havn't noticed that!

Answer 54

\( \large
(2^{i+2}-3^{j+1} )= 3(-1)^j -4(-1)^i \\\large

\text {we have 4 cases ;}\\\large {\color{Red} { \text{ case 1; i is odd j is odd}}}\\ \large
(2^{i+2}-3^{j+1} ) =1 \large
\\ {\color{Red} {\text{case 2; i is odd j is even}}}\\ \large
(2^{i+2}-3^{j+1} ) =-7 \large
\\ {\color{Red} {\text{case 3; i is even j is odd}}}\\ \large
(2^{i+2}-3^{j+1} ) =7 \large \large
\\ {\color{Red} {\text{case 1; i is even j is even}}}\\
(2^{i+2}-3^{j+1} ) =-1 \)

Answer 55

tell whats ur solution

Answer 56

see some members of X sequence:
1,1,3,5,11,21,43,85,171,...

and if u notice you will discover that members are congruent to 1,1,3,5,3,3,3,5,3,3,.. (mod 8)

and here's some members of Y:
1,7,17,55,161,487,1357,...
and for (mod 8) we have 1,7,1,7,1,7,....

so none of them can be the same except the first one = 1!

Answer 57

i see nice !

Answer 58

thanks,ur work on that functions are good ;)

Answer 59

its frustrating :P

Answer 60

well,if u want to solve another question to be calm go to my last question,i added another limit...just think about it tomorrow i'll ask it as a new question,i think it's easy but i havn't got time to work on it.

Answer 61

well i wont be online :(
preparing for final i wish first of feb to prepare some question like these :D

Answer 62

XD
well,goodnight ;) i'm tired and prefer to go to sleep :D

Answer 63

gn :)
sleep well

Answer 64

:)

Answer 65

@Loser66 ... the sequence (Y) would be:
\( Y_{n}=2(3^{n−1})+(−1)^n \)
and i checked the answer,for Y4=55 but ur function will give wrong answer ...

Answer 66

@PFEH.1999 that looks awesome ! you made it really simple by just using the mod properties xD

Answer 67

@ganeshie8 , thanks...whenever i see this sort of problems this idea come to my mind that try mod 4,8,9,13,17.... :D

Answer 68

i like 1999 number though :P
remineds me of my childhood

Answer 69

so guys i'll close the question ... thanks @Marki , ur idea was good,it can be used for other problem ;)