Message Boards Message Boards

Solve a system of recurrence relations?

Hi all!

I'm new to the Wolfram Forum community and it is a pleasure to be here.

I have a quick question for those who have expertise in the use of Mathematica....

Is Mathematica able to solve the following system of recurrence relations? I'm looking for a "closed-form" formula for w(2n+1).


For n greater than or equal to 3,

w(2n+1) = a(n+1), a(n) = 3*a(n-1) + a(n-2) - a(n-3),

a(0) = 1, a(1) = 2, a(2) = 7, w(1) = 2, w(3) = 7, and w(5) = 22.

Any help is greatly appreciated!

Sincerely, Richard M. Low

richard.low@sjsu.edu

POSTED BY: Richard Low
13 Replies

Dear @Richard Low, please spend some time learning how to properly post math notation and code on Wolfram Community:

http://community.wolfram.com/groups/-/m/t/270507

POSTED BY: EDITORIAL BOARD

Maybe so:

Solve for a[n]:

sol = First@ RSolve[{a[n] == 3*a[n - 1] + a[n - 2] - a[n - 3], a[0] == 1, a[1] == 2, a[2] == 7}, a[n], n];
Simplify[ToRadicals[(a[n] /. sol)], Assumptions -> n \[Element] Integers]

(*1/444 (2 (1 + (9 + I Sqrt[111])^(1/3)/3^(2/3) + 
  4/(27 + 3 I Sqrt[111])^(1/3))^
 n (74 + (20 74^(2/3))/(481 + 57 I Sqrt[111])^(
  1/3) + (74 (481 + 57 I Sqrt[111]))^(1/3)) + (1 + (
  I (I + Sqrt[3]) (9 + I Sqrt[111])^(1/3))/(
  2 3^(2/3)) + (-2 - 2 I Sqrt[3])/(27 + 3 I Sqrt[111])^(1/3))^
 n (148 + (20 I 74^(2/3) (I + Sqrt[3]))/(481 + 57 I Sqrt[111])^(
  1/3) + (-1 - I Sqrt[3]) (74 (481 + 57 I Sqrt[111]))^(
   1/3)) + (1 - ((1 + I Sqrt[3]) (9 + I Sqrt[111])^(1/3))/(
  2 3^(2/3)) + (-2 + 2 I Sqrt[3])/(27 + 3 I Sqrt[111])^(1/3))^
 n (148 - (20 74^(2/3) (1 + I Sqrt[3]))/(481 + 57 I Sqrt[111])^(
  1/3) + I (I + Sqrt[3]) (74 (481 + 57 I Sqrt[111]))^(1/3)))*)

Solve for w[n]:

sol2 = First@ RSolve[{w[2*n + 1] == (a[n] /. sol /. n -> n + 1), w[1] == 2, w[3] == 7, w[5] == 22}, w[n], n];
Simplify[ToRadicals[(w[n] /. sol2)], Assumptions -> n \[Element] Integers]

 (*1/222 (1 + (9 + I Sqrt[111])^(1/3)/3^(2/3) + 4/(27 + 3 I Sqrt[111])^(
     1/3))^((1 + n)/
   2) (74 + (20 74^(2/3))/(481 + 57 I Sqrt[111])^(
     1/3) + (74 (481 + 57 I Sqrt[111]))^(1/3)) + 
  1/444 (1 + (I (I + Sqrt[3]) (9 + I Sqrt[111])^(1/3))/(
     2 3^(2/3)) + (-2 - 2 I Sqrt[3])/(27 + 3 I Sqrt[111])^(1/3))^((
   1 + n)/2) (148 + (
     20 I 74^(2/3) (I + Sqrt[3]))/(481 + 57 I Sqrt[111])^(
     1/3) + (-1 - I Sqrt[3]) (74 (481 + 57 I Sqrt[111]))^(1/3)) + 
  1/444 (1 - ((1 + I Sqrt[3]) (9 + I Sqrt[111])^(1/3))/(
     2 3^(2/3)) + (-2 + 2 I Sqrt[3])/(27 + 3 I Sqrt[111])^(1/3))^((
   1 + n)/2) (148 - (
     20 74^(2/3) (1 + I Sqrt[3]))/(481 + 57 I Sqrt[111])^(1/3) + 
     I (I + Sqrt[3]) (74 (481 + 57 I Sqrt[111]))^(1/3))*)
POSTED BY: Mariusz Iwaniuk

Hello Mariusz,

You have been very helpful! Thank you.

Using your advice, w[2n+1] resolves to the following:

w[2n+1] = .0794367(.460811)^(n+1) + .255972(-.675131)^(n+1) + .664591(3.21432)^(n+1).

I do have one last question. Can Mathematica solve (ie., find a "closed-form" formula for b[k]) for the following "piecewise" defined recurrence relation?

For integers k greater than or equal to 3, b[k] = b[k-1] + b[k-3] + 2*[.0794367(.460811)^((k-1)/2) + .255972(-.675131)^((k-1)/2) + .664591(3.21432)^((k-1)/2)], if k is odd; b[k] = b[k-1] + b[k-2], if k is even; b[0] = 1, b[1] = 4, b[2] = 5.

Again, thank you very much for your help.

Solving this "piecewise" defined recurrence relation b[k] is the final part of a research project. I'm very happy to acknowledge your help within the paper and I will email you a copy of it, when I finish typing it up.

Sincerely,

Richard M. Low richard.low@sjsu.edu

POSTED BY: Richard Low

Maybe it is possible to solve with MMA yours "piecewise" defined recurrence equation. Mathematica need a lot of time to solve.My laptop is very cheap.:).I'm used a Maple to solve.

If you have a Maple I attach a file.You must have to change the file extension:

MapleSolution ver2.nb to MapleSolution ver2.mw

Good Luck.

Attachments:
POSTED BY: Mariusz Iwaniuk

Hello Mariusz,

I greatly appreciate your continual help on my question!

I looked at your two attached files (in your previous post). It is making great progress and the solution is nearly there! But, there is a small problem with the Maple/Mathematica program (probably, unexpected variable values somewhere in memory). It does not yield the correct values for b[k].

With regards to the question:

For integers k greater than or equal to 3, b[k] = b[k-1] + b[k-3] + 2*[.0794367(.460811)^((k-1)/2) + .255972(-.675131)^((k-1)/2) + .664591(3.21432)^((k-1)/2)], if k is odd; b[k] = b[k-1] + b[k-2], if k is even; b[0] = 1, b[1] = 4, b[2] = 5.

This piecewise defined recurrence relation is correct. I verified (using this piecewise defined recurrence relation, by hand calculations) the correct values: b[0]=1, b[1]=4, b[2]=5, b[3]=10, b[4]=15, b[5]=34, b[6]=49, b[7]=108, b[8]=157, b[9]=348, b[10]=505, etc.

If you have some time, can you look at your Maple/Mathematica program and see what is happening? We are so close to a "closed-form" solution to b[k] !!

I am greatly indebted to you for your valuable help.

Sincerely, Richard M. Low

POSTED BY: Richard Low

From "closed-form" solution to b[k],but only works for Odd numbers.

Attachments:
POSTED BY: Mariusz Iwaniuk

Hello Mariusz,

I'm very glad to see your attached file MMASolution-Ver4.nb, which gives a "closed-form" solution to b[k] for ODD numbers! Thank you!!

  1. In this particular "closed-form" solution (for ODD numbers), is it possible to replace all of the complicated (exact) radical expressions with simpler decimal approximations? This would yield a very compact formula which could be typeset into the research paper.

  2. Do you have any ideas for a "compact" (with simpler decimal approximations, instead of exact radical expressions) formula for b[k], for EVEN numbers?

Again, thank you for all of your help given and time spent.

Sincerely, Richard M. Low

POSTED BY: Richard Low

FullSimplify command does a good job for this.

Attachments:
POSTED BY: Mariusz Iwaniuk

This is extremely confusing. For one, the notation is not correct Mathematica so nothing can be cut-and-pasted directly. Moreover, the thread suffers from "question creep", whereby the specifics keep changing to the point where it is difficult to figure out any more what is the question under consideration. Also there seems to be no effort, or at least none shown, to adapt responses into actual RSolve code (this does not add to the confusion, but is nonetheless discouraging for what I think are obvious reasons).

Here is something that probably does what is needed, albeit in I am sure the wrong notation (but see remark on "question creep"). We get away from the odd/even issue by separating into two functions; this idea also seems to have been in some of the prior posts (again, see remark on "question creep").

a[n_] := .0794367 (.460811)^n + .255972 (-.675131)^
     n + .664591 (3.21432)^n;

rv = 
   RSolveValue[{b[n] == c[n] + c[n - 1] + 2*a[n], 
     c[n] == b[n - 1] + c[n - 2], c[0] == 1, c[1] == 5}, {b[n], c[n]}, n]

  (* Out[204]= {2.9999999999999982*2.^n + 
    Piecewise[{{(0.32057243726157714*(-675131.)^n + 
          0.055654497058256*460811.^n - 
                  1.7999987988497759*E^(14.508657738524217*n) + 
          2.423771564529943*E^(14.983126384729113*n))/
               E^(13.815510557964275*n), 
       n > 1.}}, (0.5119440000000001*(-675131.)^n + 
        0.15887340000000003*460811.^n + 
              1.329182*E^(14.983126384729113*n))/
      E^(13.815510557964275*n)] - 
    2.9999999999999982*2.^n*UnitStep[-1.*n] + 
       C[1]*
     UnitStep[-1.*
       n], (-1.0000005443826219*(-0.3977012401567452*(-675131.)^n*
         E^(0.7747672983575988*n) + 
             0.03256025590597696*E^(13.815510557964275*n) + 
        1.*(-1.)^n*E^(14.590277856321874*n) - 
             1.9999989112353476*2.^n*E^(14.590277856321874*n) + 
        1.1999985459748292*E^(15.283425036881816*n) - 
             0.8348581061063877*E^(15.757893683086712*n)))/
    E^(14.590277856321874*n)} *)

Check the result numerically:

Table[rv, {n, 0, 6}]

(* Out[206]= {{1.9999994 + C[1], 1.}, {9.9999976319, 5.}, {29.9999920347,
   10.9999976319}, {89.9999745305, 34.9999920347}, {277.999927528, 
  100.999972162}, {869.999809803, 312.999919563}, {2749.99955564, 
  970.999781965}} *)
POSTED BY: Daniel Lichtblau

Hi Daniel,

I apologize for the confusing "thread creep". After consolidating all of the helpful answers (thus far) to my original question, here is the MAIN QUESTION (in concise language):

Find a formula (in compact form; for example: a[n] = .0794367(.460811)^n + .255972(-.675131)^n + .664591(3.21432)^n) which solves the following piecewise-defined recurrence relation b[k]: For integers k greater than or equal to 3, b[k] = b[k-1] + b[k-3] + 2*[.0794367(.460811)^((k-1)/2) + .255972(-.675131)^((k-1)/2) + .664591(3.21432)^((k-1)/2)], if k is odd; b[k] = b[k-1] + b[k-2], if k is even; b[0] = 1, b[1] = 4, b[2] = 5.

I verified (using this piecewise defined recurrence relation, by hand calculations) the correct values: b[0]=1, b[1]=4, b[2]=5, b[3]=10, b[4]=15, b[5]=34, b[6]=49, b[7]=108, b[8]=157, b[9]=348, b[10]=505, etc.

Again, I appreciate all of the help that everybody has given me thus far! We almost have the answer to my question.

Sincerely, Richard M. Low

POSTED BY: Richard Low

With RSolve you solve for a(n), and then w(k)=a((k-1)/2). Finally you check whether the initial conditions for w are met. To get you started:

RSolve[{a[n] == 3*a[n - 1] + a[n - 2] - a[n - 3], a[0] == 1, 
   a[1] == 2, a[2] == 7}, a, n]
POSTED BY: Gianluca Gorni

Hello Gianluca,

Thank you for your quick reply. I tried your suggestion and Mathematica 11 gives a strange output format. Eventually, I was able to squeeze the answer out by using WolframAlpha, believe it or not!

Now, the main question is the following: Can Mathematica solve (for b[k] and c[r]) the following system of recurrence relations? b[k] is defined for only odd natural numbers, and c[r] is defined for only even non-negative integers.

For n greater than or equal to 3; b[2n+1] = c[2n] + c[2n-2] + 2*a[n], c[2n] = b[2n-1] + c[2n-2], a[n] = .0794367(.460811)^n + .255972(-.675131)^n + .664591(3.21432)^n;

c[0]=1, b[1]=4, c[2]=5, b[3]=10, c[4]=15, b[5]=34.

I seemed to have tried "everything" in Mathematica 11 and WolframAlpha, but nothing seems to work.... Any help is greatly appreciated!

Sincerely, Richard M. Low

POSTED BY: Richard Low

You really should show what you tried. It's not the sort of thing I'd want to guess at.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract