2
$\begingroup$

Actually, I will be asking two, but related, questions.

Question 1. Is there some theory about recurrent relations with several indices. For example, If we have a relation on $A_{i;j}$: $$A_{i+\alpha; j+\beta} = F(A_{i+\alpha-1;j+\beta -1}, \ldots, A_{i;j}).$$

And related

Question 2. Let $m, n$, $Q_{m}^ {n}\in \mathbb{N}$. Then solve given 2-recurrent relation: $$Q_{m}^{n+1} = 2Q_{m}^{n} + Q_{m-1}^{n}$$ with the following conditions on $Q$: \begin{align} Q_{j}^{j} &= 1,\\ Q_{k}^{l} &= 0,\quad \text{for } k>l. \end{align}

I have solved the last problem by pattern recognition followed by induction , two ways that I do not like to prove something. I would like to get more rough method.

This relation naturally appeared when I tried to count the number of $m$-dim edges in $n$-dim cube (vertex is $0$-dim, edge - 1-dim. square - $2$-dim and etc). In this context the answer is obvious I think. I will post my solution below.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ typically one would use a multivariate generating function for these kinds of problems. $\endgroup$
    – Dima Pasechnik
    Mar 6, 2017 at 9:35
  • $\begingroup$ My solution in the context of $n$-dim cube is the following. Obviously, that there are $2^n$ vertices in $n$-dim cube. Then at each vertex choose $m$ $1$-dim edges which are part of $m$-dim cube. You will obtain $2^n C_{n}^{m}$. But you should divide this number by the number of how many times the same $m$ -dim cube was added in total sum which is $2^m$. Voilà, $Q_{n}^{m} = 2^{n-m}C_{n}^{m}.$ $\endgroup$
    – LRDPRDX
    Mar 7, 2017 at 9:35

1 Answer 1

Reset to default
4
$\begingroup$

This was an answer before the typo was edited by the OP on $Q_m^{n+1}=2Q_m^n+Q_{m-1}^{n-1}$.

Let $F(x,y)=\sum_{n,m\geq0}Q_n^mx^my^n$ be a generating function. Based on the recurrence relation alone, you should be getting $$F(x,y)=\frac{P(x,y)}{1-2y-xy^2};$$ for some polynomial $P(x,y)$ which depends on the initial conditions (this, I leave up to you).

Caveat. You last initial condition does not sync with the recurrence. For example, $Q(3,3)=2Q(3,2)+Q(2,1)=0$ but supposedly $Q(3,3)=1$ and $Q(3,2)=Q(2,1)=0$. A mismatch!

===============================

After the edit by OP: $Q_m^{n+1}=2Q_m^n+Q_{m-1}^n$. Again, let $F(x,y)=\sum_{n,m\geq0}Q_n^mx^my^n$ be a generating function. Based on the recurrence relation alone, you should be getting $$F(x,y)=\frac{P(x,y)}{1-2y-xy}=P(x,y)\sum_{n=0}^{\infty}(2+x)^ny^n =P(x,y)\sum_{m,n\geq0}\binom{n}m2^{n-m}x^my^n;$$ for some polynomial $P(x,y)$ which depends on the initial conditions ($P=1$, I think). Therefore, $Q_m^n=\binom{n}m2^{n-m}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Good catch! I fixed this typo. I will try with generating function. $\endgroup$
    – LRDPRDX
    Mar 6, 2017 at 10:13
  • $\begingroup$ Thank you for this solution. I obtained the same result before. Now I can reveal the motivation. I will add it in the question description, $\endgroup$
    – LRDPRDX
    Mar 6, 2017 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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