0

If I have a recurrence relation like $$T(n,k)=\frac{T(n-1,k)+T(n,k-1)}{2}$$ with initial values $\forall n \quad T(n,0)=T_0$ and $\forall k \quad T(0,k)=0$. How can I solve it? By the way this came up when I was solving a physics problem

Armando j18eos
  • 3,907
spitfire
  • 13
  • 1
    Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please [edit] the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – José Carlos Santos Jun 20 '20 at 08:53
  • @JeanMarie's answer points out we also need $T_{0,,p}$ for $p>0$. My guess is you want these to be $0$. But whether I'm right or not, your question should address this boundary too. – J.G. Jun 20 '20 at 09:32
  • $T_{0,p}$ is $0$ @J.G. – spitfire Jun 20 '20 at 14:11
  • @spitfire In that case, you might want to work out a recursion relation in a sequence $p_n$ of polynomial functions of $k$ satisfying $T(n,,k)=T_0p_n(k)/2^{n+k-1}$. – J.G. Jun 20 '20 at 14:41
  • @J.G. but what is $p_n$? Polynomial functions of $k$? Sorry but I didn't get what are these. I'm not a mathematician I'm a physicist – spitfire Jun 20 '20 at 14:53
  • @JoséCarlosSantos I edited my question and there's no doubts I think – spitfire Jun 20 '20 at 14:55
  • @spitfire: Here's a different approach... There's a simple book that explains a lot about these types of recurrence relations called "generatingfunctionology". You can get a free copy of the book at https://www.math.upenn.edu/~wilf/DownldGF.html In particular, check out section 1.4, which expains two-term functions. I hope that this may help. – Matt Groff Jun 22 '20 at 01:00
  • Follow approach from here https://math.stackexchange.com/questions/2065067/solving-two-dimensional-recurrence-relation-a-i-j-a-i-j-1-a-i/2065193#2065193. Also warning, you will need to get your definitions straight. As currently written, it is unclear what is $T(0,0)$, is it $T_0$ or $0$? – Sil Jun 22 '20 at 10:47

1 Answers1

1

Here is a graphical representation of your recurrence relationship :

enter image description here

(which, now that you have settled correctly your initial data, isn't compulsory, but is interesting by itself because it shows its similarity with the ¨Pascal's triangle" (see below).

Some numerical computations on the first values of $T_{n,k}$ in the case of $T_0=1$ give the following first numerical results with denominators $2^{n+k-1}$.

(please note the diagonal values equal to $1/2$) :

enter image description here

Out of this array, we can build a simplified one by turning it $135°$clockwise in the "Pascal's triangle' manner and keeping only the numerators where the right diagonal, instead of being filled by "ones", is filled by successive powers of $2$ :

$$\begin{array}{ccccccccc} &&&&&1&&&&\\ &&&&\color{blue}{1}&&\color{red}{2}&&&&&\\ &&&\color{blue}{1}&&3&&\color{red}{4}&&&&&&&&\\ &&\color{blue}{1}&&4&&7&&\color{red}{8}&&&\\ &\color{blue}{1}&&5&&11&&15&&\color{red}{16}&&&\\ \color{blue}{1}&&6&&16&&26&&31&&\color{red}{32} \end{array}\tag{1}$$

We have simplified the problem because in this way only integers are managed, and (thanks to an indication by the OP) this is known in the litterature under the name "Bernoulli triangle" yielding the explicit formula for the coefficients in the previous "Pascal's like" array (1) (it is why we write $T'$ instead of $T$):

$$\displaystyle T'_{n,k}=\frac{1}{2^{n}}\sum _{p=0}^{k}{\binom {n}{p}} \ \ \text{for} \ \ k=0,1,\cdots n$$

Jean Marie
  • 81,803
  • I'm sorry for not writing it in my question @Jean Marie – spitfire Jun 20 '20 at 14:12
  • I'm sorry but this wasn't clear to me. So why do we need that graphical represantation? how can we solve the recurrence relation? – spitfire Jun 20 '20 at 14:16
  • I get what you wrote there, but how can I find $T_{n,k}$ in terms of $n$,$k$,$T_0$.I've searched about wave propagation with damping but i didn't find anything. So can you explain more? by the way what you mean numerical value for $T_{0,q}$ they are all zeros – spitfire Jun 20 '20 at 14:46
  • 1
    And all the $T(n,0)$ is not equal to $0$ it's equal to $T_0$ – spitfire Jun 20 '20 at 15:06
  • I have improved the approach by reducing the issue to a pure integer question (In the case $T_0=1$). But I still doubt there is a closed form expression for the general term. – Jean Marie Jun 22 '20 at 07:31
  • 1
    I find solution to this problem : https://cdn.discordapp.com/attachments/719928959256625232/724081817828851758/potd_193.pdf – spitfire Jun 22 '20 at 11:20
  • Therfore the keyword for what I had found is "Bernoulli triangle", with a formula for $T_{n,k}$ that still contains a "\Sigma".. – Jean Marie Jun 22 '20 at 18:22