Skip to main content
4 of 6
edited title
LRDPRDX
  • 251
  • 1
  • 6

Recurrent relation with several indices ( How many $m$-dim cubes in $n$-dim cube )

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_{0}^{n} &= 2^n\\ 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, square - $2$-dim and etc). In this context the answer is obvious I think. I will post my solution below.

LRDPRDX
  • 251
  • 1
  • 6