Drawing at least two consecutive numbers (in order) with n possible numbers and k draws with replacement Say you draw a random number out of n, and you do this k times.
I want to know the probability of getting at least two consecutive numbers in consecutive order of the draws.
This problem just popped into my head, I haven't done any math in years and English isn't my first language, so bear with me regarding the phrasing.
Here's an example to illustrate:
You pick a random number from 1 to 10 and do this 5 times, so $n=10$ and $k=5$.
Examples of rounds that would count as a success are:
7, 2, 3, 9, 3
5, 6, 7, 7, 2
etc. Examples of rounds that do not count as a success are:
4, 9, 8, 1, 6
1, 1, 5, 2, 8
etc. So two consecutive numbers have to be drawn in two consecutive draws in the right order.
I spent a while trying to figure this out and came up with this:
$$1- \left(\frac 1n + \frac{(n-1)^2}{n^2}\right)^{k-1}$$
My thinking was that for any draw there is a certain probability to not get the number that is "one higher" than the previous number. If the previous number is the highest possible number, the probability is 0. If the previous number is any other number, which it is in $\frac{n-1}{n}$ cases, the probability is $\frac{n-1}{n}$. Therefore for any draw the probability to not get a number that is one higher than the previous number is $\frac 1n + \frac{(n-1)^2}{n^2}$. This is true for all draws but the first, since there is no previous number. That's why that has to happen $k-1$ times in a row for the round to be a non-success. The inverse would therefore be the probability for my question.
The probabilities this formula gives me are pretty close to the actual numbers I get when I play it through, which leads me to believe it's not completely wrong. But I drew a tree diagram for $n=3$ and $k=3$ and counted all possible outcomes. In 11 out of 27 possible combinations you get at least two consecutive numbers in two consecutive draws, so the probability is $\frac{11}{27}=0.407$. But my formula gives me $0.395$.
I hope what I'm asking is clear and I'd be grateful if somebody can tell me what I've missed! Thanks!
 A: In this answer, I'll mainly explain what's wrong with your computation at greater length than I did in my comment.  I'll suggest a solution method at the end.  
Let $X_i$ be the random variable whose value is the outcome of draw number $i$, for $i=1,\dots,k$.  Let $Y_i$ be the event that $X_{i+1}\neq X_i+1,\ i=1,\dots,k-1$.  Let 
$Z_i=\bigcap_{j=1}^iY_i,\ i=1,\dots,k-1$, so that the probability we want is $1-\Pr(Z_{k-1})$.
It's easy to compute $\Pr(Z_1)$.  There are $n^2$ equally likely sequences of two draws, and all but $n-1$ of them are acceptable, so $$\Pr(Z_1)=\frac{n^2-n+1}{n^2}.$$
Now $$\Pr(Z_2)=\Pr(Z_1\cap Y_2)=\Pr(Y_2|Z_1)\Pr(Z_1),$$ so we need to compute $\Pr(Y_2|Z_1)$.  Of the $n^2$ possible sequences of two draws, $n$ end with each possible value.  The $n-1$ events we have excluded end in each possible value except $1$.  That is, $$\Pr(X_2=i|Z_1)=\begin{cases}
\frac{n}{n^2-n+1},&i=1\\
\frac{n-1}{n^2-n+1},&1<i\leq n\end{cases}$$ The important thing is that $\Pr(X_2=n|Z_1)=\frac{n-1}{n^2-n+1}$ so that $$\Pr(Y_2|Z_1)= \frac{n-1}{n^2-n+1} +\frac{n-1}n\cdot\frac{n^2-2n+2}{n^2-n+1}$$
We can compute $\Pr(Z_2)$ now, but things get successively more complicated.  Since $$\Pr(X_2=1|Z_1)>\Pr(X_2=2|Z_1),$$ we will also have $$\Pr(X_3=2|Z_2)<\Pr(X_2=3|Z_2),$$ and we'll still have $$\Pr(X_3=2|Z_2)>\Pr(X_2=1|Z_2),$$ so that computing $\Pr(X_3=n|Z_2)$ will be more complicated.
It's possible to model this, at least for specific values of $n$ and $k$ as a finite-state, absorbing Markov chain.  There are $n$ transient states, corresponding to the value of the last draw, and one absorbing state, corresponding to getting two consecutive numbers in consecutive draws.  The initial vector has probability of $1/n$ in each of the transient states, and then we compute the probability of non-absorption in $k-1$ more steps.  With a computer algebra system, you can get exact values for the probability, so long as $n$ and $k$ didn't get too large.  
I did this with python and sympy in order to be sure of getting exact arithmetic.
from itertools import product
from sympy import ones
from fractions import Fraction

def actual(n,k):
    answer = 0
    for p in product(range(n), repeat=k):
        if any(p[i+1]== q+1 for i, q in enumerate(p[:-1])):
            answer += 1
    return 1- answer/n**k


def expected(n,k):
    # multiply everything by n to work with integers
    M = ones(n+1,n+1)
    for j in range(n):
        M[j,j+1]=0
        M[n,j] = 0
    M[n,n] = n
    X = ones(1,n+1)
    X[0,n] = 0
    for _ in range(k-1):
        X = X@M
    return 1- X[0,n]/ n**k

def test(n, k):
    a = actual(n,k)
    e = expected(n, k)
    if a== e: 
        print('Okay')
    else:
        print(f'Actual {a}; expected {e}')

The expected function computes the desired probability.  The actual and test functions are just for testing on small $n,k$.
I got a this answer for expected(100,15) rather quickly:
$$106198124370595359469817949/122070312500000000000000000$$
It took somwhat longer to compute expected(100,100).  However, as the numerator has $170$ digits and the denominator $171$, it's not worth listing here.  The floating point value was $0.3734449240882214.$
I wonder if $$\lim_{n\to\infty}expected(n,n)=1/e$$ 
