0
$\begingroup$

I'm trying to find an analytical solution which depends only of $i,j$ and $a$ variables, for a serie considering some initial assumptions.

The series is

$$s_{i0}=s_{0j} = 1,\\ s_{11} = 1-a,\\ s_{12} = a,\\ s_{ij} = \sum_{k=1}^2 s_{1k}s_{(j-k)i},$$

for $i = 2\ldots N$, $j=1\ldots 2$, $s_{i0}=s_{0j} = 1$ and $s_{ij}=0$ if $i<0$ or $j<0$.

I tried coding like this:

s[1, 1] := 1 - a;
s[1, 2] := a;
s[i, 0] := 1;
s[0, j] := 1;

s[i, j] = Refine[Sum[s[1, k] s[i - k, j], {k, 1, 2}],Assumptions -> {i >= 2, 1 <= j <= 2}]

But I only get the result

a s[-2 + i, j] + (1 - a) s[-1 + i, j]

which is in function of the previous $s_{ij}$ and its look like the assumptions are not taken in account (because of the s[-2 + i, j] and s[-1 + i, j] which are assuming negative index values).

I'm new in Mathematica, and if you guys could help I'll be much appreciated.

$\endgroup$
1
$\begingroup$

Although it is okay to use the ":=" or SetDelayed command, the plain Set command "=" may be simpler for the first few statements, because they have constants on the RHS. So, we begin with

ClearAll["Global`*"]
s[1, 1] = 1 - a;
s[1, 2] = a;

For the next two statements we need to use the Blank[] expression, which is abbreviated with the underscore, as

s[_, 0] = 1;
s[0, _] = 1;

In the above, there is no need to name the blank, since the name does not appear on the RHS.

Now we can code

s[i_, j_] := Simplify[Sum[s[1, k] s[i - k, j], {k, 1, 2}]]

Here, we need to name the blanks and use the the ":=" symbol, because $i$ and $j$ appear on the RHS. Also, we could have coded this SetDelayed before the Set statements, but the more general cases are usually defined after the more specific cases.

Now we can try to find s[1,3], but if we do we will get an error, because we have left something out. When $i$ is 1 and $k$ is 2, we get an s[-1,3] in our sum, and that is a problem.

So, we can add the statement s[-1,_] = 0;
Now we can make a table of values of $s_{ij}$ like this

t = Table[s[irow, jcol], {irow, 0, 4}, {jcol, 1, 3}]
t // TableForm

$\begin{array}{ccc} 1 & 1 & 1 \\ 1-a & a & 1-a \\ a^2-a+1 & -(a-2) a & a^2-a+1 \\ -a^3+a^2-a+1 & a \left(a^2-2 a+2\right) & -a^3+a^2-a+1 \\ a^4-a^3+a^2-a+1 & -a \left(a^3-2 a^2+2 a-2\right) & a^4-a^3+a^2-a+1 \\ \end{array}$

Edit 1:

Also, since the expression for s[i,j] is a recursion relation, to avoid recalculating the values of $s_{ij}$ you may want to use

s[i_, j_] := s[i, j] = Sum[s[1, k] s[i - k, j], {k, 1, 2}] // Simplify

instead of the first definition. This new definition tells MMA to save the intermediate values, which uses more memory, but will be faster if you need to calculate many values $s_{ij}$ for large $i$ and $j$.

Edit 2:

Now claim there are only two unique columns in any table t with any number of rows and columns calculated as above. This conjecture seems obvious by inspection using a large number of rows and column. Here's how we can verify the claim for a few rows and columns. First take the transpose, which gives a list of the columns. Then drop the second element and use Union to get a list of unique columns. There is only one element, so there is only one unique column, except for the second column. Here's the code:

t = Table[s[irow, jcol], {irow, 0, 50}, {jcol, 1, 30}];
Drop[Transpose[t], 2] // Union // Length

A second conjecture is the $i$-th row of the first column can be written as $s_{i,1}=\Sigma_{k=0}^i(-a)^k$. We can find another form for this expression with

Sum[(-a)^k, {k, 0, i}]//Factor

$\frac{a (-a)^i+1}{a+1}$

That's the closed form for the $s_{i,j\neq 2}$. We can get a closed form for $s_{i2}$ by a third conjecture that the $i$-th row of the second column of table $t$ is $s_{i,2}=2+(-a)^i-2\Sigma_{k=0}^i(-a)^k$. Here's the code

Factor[ 2 + (-a)^i - 2 Sum[(-a)^k, {k, 0, i}] ]

$\frac{(-a)^i+(-a)^{i+1}+2 a}{a+1}$

To prove the conjectures using Mathematica, searching this forum for "induction" would be a good first step. Also, replacing $a$ with $-b$ from the beginning could make the expressions simpler in an induction proof.

$\endgroup$
4
  • $\begingroup$ LouisB, your answer clarified me a lot about the language. Thank you very much. My only question now is that if I can find a general solution for the series that only depends of $a$,$i$ and $j$. The general solution that mathematica found was: s[i,j] = a s[-2 + i, j] - (-1 + a) s[-1 + i, j] I'm trying to find a general solution which looks like: s[i,j] = a [something in function of 'a','i' and 'j'] - (-1 + a) [something in function of 'a','i' and 'j'] But I dont know if the series above can be wrote in this way. $\endgroup$ Jun 12 '19 at 20:24
  • $\begingroup$ Correcting my last comment. I want to find something like: s[i,j] = a [something in function of 'a','i' and 'j'] - (-1 + a) [something in function of 'a','i' and 'j'] for $i\geq2$ and $1\leq j\leq2$. $\endgroup$ Jun 12 '19 at 20:32
  • $\begingroup$ Look at the column $s_{i,1}$ . It is the same as all the other columns, except for column $s_{i,2}$. It looks like there could be one closed form expression for $s_{i,2}$ and another closed form for the other columns. I am ignoring column $s_{i,0}$, which is all ones. Maybe Mathematica can find the closed forms, maybe not. $\endgroup$
    – LouisB
    Jun 12 '19 at 20:42
  • $\begingroup$ It looks like the second column is $s_{i,2}=2+(−a)^i−2\Sigma(−a)^k$ and the other columns are $s_{i,j}=\Sigma(−a)^k$ when $j\neq 2$, with the sums over $k$ running from 0 to $i$, but I haven't checked it. Earlier comment said 1 to $k$, which was clearly wrong. $\endgroup$
    – LouisB
    Jun 12 '19 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.