# A difference equation related to RW on Hypercube

I am trying to solve the following recurrent relation $$T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0$$

Where $0\leq n\leq m$ and $m$ is a fixed integer. I have written the relation as a difference equation as it is often a way to solve these, and so for $D(n)=T(n)-T(n+1)$ I get $$D(n)=\frac{n}{m-n}D(n-1)+\frac{m}{m-n}.$$ Now I want to sum on both side to telescop the sum and use the fact that $T(m)=0$ but my problem is that on the right side, $D(-1)$ is not defined.

The goal of this problem is to find the hitting time from (0,...0) to (1,...,1) for a simple random walk on the $m$-dimensional hypercube and so $T(n)$ represents this (expected) hitting time.

Thanks

-
I found this article which kinda does what I want to do, but I don't know how he gets to line (11) arxiv.org/pdf/quant-ph/0510136.pdf – Jean-Sébastien Jul 26 '12 at 2:54

The expected time to go from $(0,\dots,0)$ to $(1,\dots,1)$ is
$$\sum_{k=1}^m \left[k{m\choose k}\right]^{-1} \cdot \sum_{k=1}^m k{m\choose k} =2^{m-1} \sum_{k=1}^m {m-1\choose k-1}^{-1}={m\over 2}\sum_{k=1}^m{2^k\over k} .$$