What is the Linear Combination of Recursive Series?

[ramsey2879]

Let there be two recursive series S and R as follows:

$$S_{0} = 0 \quad S_{1} = s \quad S_{n} = 6S_{n-1} - S_{n-2} + p$$
$$R_{0} = 0 \quad R_{1} = t \quad R_{n} = 6R_{n-1} - R_{n-2} + p$$

Prove $$S_{n}*(R_{n+1} + t - p) = R_{n}*(S_{n+1} + s - p)$$

 

[dodo]

Sn is a linear combination of s and p, as Rn is of t and p. In fact, they can be written as

$$\begin{align*} S_n &= s A_n + p B_n \\ R_n &= t A_n + p B_n \end{align*}$$​

where

$$\begin{align*} A_n &= 6 A_{n-1} - A_{n-2} & "(Sloane A001109)" \\ B_n &= 6 B_{n-1} - B_{n-2} + 1 \end{align*}$$​

A few things can be said about An and Bn. It is easy to prove by induction that

$$B_n = \sum_{i=1}^{n-1} A_i$$​

Thus $B_{n+1} = A_n + B_n$.
Since $B_{n+1}$ is also $6 B_n - B_{n-1} + 1$,
we have $A_n = 5 B_n - B_{n-1} + 1$.

From the above, it is possible to work by induction to prove

$$B_n (B_n - 1) = B_{n+1} B_{n-1}$$​

and from here, to arrive by substitution to

$$A_n (B_{n+1} - 1) = B_n (A_{n+1}+1)$$​

At this point it is possible to use these results to prove your claim. It is best to rule out first two simpler cases, (1) s=t and (2) p=0, and finally, the case where both s$\neq$t and p$\neq$0.

More specifically, you'll arrive to something like

$$p (s-t) \left( A_n B_{n+1} - A_n - B_n - A_{n+1}B_n \right) = 0$$​

 

[ramsey2879]

Let there be two recursive series S and R as follows:

$$S_{0} = 0 \quad S_{1} = s \quad S_{n} = 6S_{n-1} - S_{n-2} + p$$
$$R_{0} = 0 \quad R_{1} = t \quad R_{n} = 6R_{n-1} - R_{n-2} + p$$

Prove $$S_{n}*(R_{n+1} + t - p) = R_{n}*(S_{n+1} + s - p)$$

I also discovered that "p" can be different for S and R so let p1 correspond to S and p2 correspond to R. My identity becomes

$$S_{n}*(R_{n+1}+t -p2) = R_{n}*(S_{n+1} + s - p1)$$

 

[ramsey2879]

Also any integer can be substituted for the 6 in the recursive formula

 

[dodo]

I was wondering about that. Now what about a second integer coefficient (i.e. other than -1) on the n-2 term?

 

[MathematicalPhysicist]

why not look at:
T(n)=S(n)-R(n)=6(S(n-1)-R(n-1))-(S(n-2)-S(n-1))=6T(n-1)-T(n-2)
T(0)=0
T(1)=s-t
solve for T(n), and now you have a connection between S(n) and R(n), then you can write S(n)=R(n)+(solution of T(n)) and then you write each side of the equation with only one of the expressions which is much easier than both S and R, i think it should be easier, did'nt try it myself though.

 

[ramsey2879]

I was wondering about that. Now what about a second integer coefficient (i.e. other than -1) on the n-2 term?

I tried integers from -9 to 9 for the n-2 term multiplier but only -1 worked. I will work more on the theory now. By the way the LaTex graphic for the A(n) and B(n) definition in your first post doesn't generate on my computer. Is there a problem with it?

 

[dodo]

Yes, thanks. It was supposed to be

$$\begin{align*} A_0 = 0; \ \ \ A_1 = 1; \ \ \ & A_n = 6 A_{n-1} - A_{n-2} & \mbox{ (Sloane A001109) } \\ B_0 = 0; \ \ \ B_1 = 0; \ \ \ & B_n = 6 B_{n-1} - B_{n-2} + 1 \end{align*}$$​

It showed in the preview, but not in the post. I just thought it was some server load issue. And it was incomplete anyway. And my LaTex sucks.

BTW, did you follow the same route for the proof? Mine was too long. Maybe using the closed form of the sequences is faster, but that's beyond me.

 

[ramsey2879]

Yes, thanks. It was supposed to be

$$\begin{align*} A_0 = 0; \ \ \ A_1 = 1; \ \ \ & A_n = 6 A_{n-1} - A_{n-2} & \mbox{ (Sloane A001109) } \\ B_0 = 0; \ \ \ B_1 = 0; \ \ \ & B_n = 6 B_{n-1} - B_{n-2} + 1 \end{align*}$$​

It showed in the preview, but not in the post. I just thought it was some server load issue. And it was incomplete anyway. And my LaTex sucks.

BTW, did you follow the same route for the proof? Mine was too long. Maybe using the closed form of the sequences is faster, but that's beyond me.

It seems that a proof is more involved now that we added more variables to the mix
I like the $$A_{n}$$ and $$B_{n}$$ approach but we need to rephase it using x in place of 6.
There are two tables of coefficients for A_n and B_n each are triangular with T{i,j) = T(i-1,j-1) - T(i-1,j) for j > 0. The left hand column, (j=0) alternates between 1 and -1 for A_n and between 1 and 0 for B_n.
Table of coefficients for $$A_{n}$$
1
-1 1
1 -2 1
-1 3 -3 1
1 -4 6 -4 1
...
The powers of x increase from left to right
You use diagonal lines through this table with a slope of 1 down to 2 across

A(1) = 1
A(2) = x
A(3) = -1 + x^2
A(4) = -2x+x^3
A(5) = 1 -3x^2 + x^4
...

Table of coefficients for $$B_{n}$$

1
0 1
1 -1 1
0 2 -2 1
1 -2 4 -3 1

Here there are two adjacent diagonal lines that make up the polynomial in x

B(2) = 1
B(3) = 1 + x
B(4) = x+ x^2
B(5) = -x + x^2 + x^3
...

I got to close now.

 

[MathematicalPhysicist]

have you even tried my suggestion, cause it seems this appraoch gets you nowhere.

p.s
do you know how to solve recursive equations?

 

[ramsey2879]

have you even tried my suggestion, cause it seems this appraoch gets you nowhere.

p.s
do you know how to solve recursive equations?

I thought of that but the solution I knew was for basic equations with the d variable equal to 0. The known solution would be for $$S_{n} = bS_{n-1} - S_{n-2} + d$$ for d = 0.
Now that you mention it I went back to figure how to add a constant to each term of my series to get to a recursive series that has 0 for the d variable.
Thus I found that if I add $$\frac{d}{b-2}$$ to each term of my series I obtain a new series with the same auxiliary equation $$x^2-bx+1 = 0$$ with roots $$r_{1} , r_{2}$$ but with d = 0. Then A and B are found by solving the following set of equations;
$$S_{n} = Ar_{1}^{n} + Br_{2}^{n} - \frac{d}{b-2}$$

Do you agree with this?

 

[ramsey2879]

Sn is a linear combination of s and p, as Rn is of t and p. In fact, they can be written as

$$\begin{align*} S_n &= s A_n + p B_n \\ R_n &= t A_n + p B_n \end{align*}$$​

where

$$A_{0} = 0 \quad A_{1} = 1 \quad A_{n} = 6 A_{n-1} - A_{n-2}$$
$$B_{0} = B_{1} = 0 \quad B_{n} = 6 B_{n-1} - B_{n-2} + 1$$

A few things can be said about An and Bn. It is easy to prove by induction that

$$B_n = \sum_{i=1}^{n-1} A_i$$​

Thus [tex]B_{n+1} = A_n + B_n[/itex].
Since $B_{n+1}$ is also $6 B_n - B_{n-1} + 1$,
we have $A_n = 5 B_n - B_{n-1} + 1$.

From the above, it is possible to work by induction to prove

$$B_n (B_n - 1) = B_{n+1} B_{n-1}$$​

and from here, to arrive by substitution to

$$A_n (B_{n+1} - 1) = B_n (A_{n+1}+1)$$​

At this point it is possible to use these results to prove your claim. It is best to rule out first two simpler cases, (1) s=t and (2) p=0, and finally, the case where both s$\neq$t and p$\neq$0.

More specifically, you'll arrive to something like

$$p (s-t) \left( A_n B_{n+1} - A_n - B_n - A_{n+1}B_n \right) = 0$$​

I looked this over again and it indeed does prove my identity even for the added variables. Thanks for your effort. PS I simplified the LaTex that didn't take for some reason. I think your LaTex is much better than mine though.

Again I thank you.