Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive Series Equality

  1. Oct 4, 2007 #1
    Let there be two recursive series S and R as follows:

    [tex]S_{0} = 0 \quad S_{1} = s \quad S_{n} = 6S_{n-1} - S_{n-2} + p [/tex]
    [tex]R_{0} = 0 \quad R_{1} = t \quad R_{n} = 6R_{n-1} - R_{n-2} + p [/tex]

    Prove [tex]S_{n}*(R_{n+1} + t - p) = R_{n}*(S_{n+1} + s - p)[/tex]
     
  2. jcsd
  3. Oct 5, 2007 #2
    Sn is a linear combination of s and p, as Rn is of t and p. In fact, they can be written as
    [tex]\begin{align*}
    S_n &= s A_n + p B_n \\
    R_n &= t A_n + p B_n
    \end{align*}[/tex]​
    where
    [tex]
    \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*}
    [/tex]​
    A few things can be said about An and Bn. It is easy to prove by induction that
    [tex]B_n = \sum_{i=1}^{n-1} A_i[/tex]​
    Thus [itex]B_{n+1} = A_n + B_n[/itex].
    Since [itex]B_{n+1}[/itex] is also [itex]6 B_n - B_{n-1} + 1[/itex],
    we have [itex]A_n = 5 B_n - B_{n-1} + 1[/itex].

    From the above, it is possible to work by induction to prove
    [tex]
    B_n (B_n - 1) = B_{n+1} B_{n-1}
    [/tex]​
    and from here, to arrive by substitution to
    [tex]
    A_n (B_{n+1} - 1) = B_n (A_{n+1}+1)
    [/tex]​

    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[itex]\neq[/itex]t and p[itex]\neq[/itex]0.

    More specifically, you'll arrive to something like
    [tex]
    p (s-t) \left( A_n B_{n+1} - A_n - B_n - A_{n+1}B_n \right) = 0
    [/tex]​
     
    Last edited: Oct 5, 2007
  4. Oct 5, 2007 #3
    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

    [tex] S_{n}*(R_{n+1}+t -p2) = R_{n}*(S_{n+1} + s - p1)[/tex]
     
  5. Oct 6, 2007 #4
    Also any integer can be substituted for the 6 in the recursive formula
     
  6. Oct 6, 2007 #5
    I was wondering about that. Now what about a second integer coefficient (i.e. other than -1) on the n-2 term?
     
  7. Oct 6, 2007 #6
    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.
     
  8. Oct 6, 2007 #7
    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?
     
  9. Oct 7, 2007 #8
    Yes, thanks. It was supposed to be
    [tex]
    \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*}
    [/tex]​
    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.
     
    Last edited: Oct 7, 2007
  10. Oct 8, 2007 #9
    It seems that a proof is more involved now that we added more variables to the mix
    I like the [tex]A_{n}[/tex] and [tex]B_{n}[/tex] 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 [tex] A_{n}[/tex]
    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 [tex]B_{n}[/tex]

    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.
     
    Last edited: Oct 8, 2007
  11. Oct 9, 2007 #10
    have you even tried my suggestion, cause it seems this appraoch gets you nowhere.

    p.s
    do you know how to solve recursive equations?
     
  12. Oct 9, 2007 #11
    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 [tex]S_{n} = bS_{n-1} - S_{n-2} + d[/tex] 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 [tex]\frac{d}{b-2}[/tex] to each term of my series I obtain a new series with the same auxiliary equation [tex]x^2-bx+1 = 0[/tex] with roots [tex] r_{1} , r_{2}[/tex] but with d = 0. Then A and B are found by solving the following set of equations;
    [tex]S_{n} = Ar_{1}^{n} + Br_{2}^{n} - \frac{d}{b-2}[/tex]

    Do you agree with this?
     
    Last edited: Oct 9, 2007
  13. Oct 10, 2007 #12
    [tex]A_{0} = 0 \quad A_{1} = 1 \quad A_{n} = 6 A_{n-1} - A_{n-2}[/tex]
    [tex]B_{0} = B_{1} = 0 \quad B_{n} = 6 B_{n-1} - B_{n-2} + 1[/tex]
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Recursive Series Equality
Loading...