Deduction of the fast recurrence 

In the basic recurrence, k is a constant parameter and n varies. So we can write T(n) instead of T(n,k):
(1) T(1) = 1,  T(n) = 1 + [T(n-1)+k-1] mod n.
The sought term is T(N), where N is a given value.

Fast recurrence (with line numbers for reference):
1  z(1)=1, r(1)= 1 
2  for m>=1:
3  if z(m)<k-1 then
4    z(m+1)=z(m)+1
5    r(m+1)=1+[r(m)+k-1] mod z(m+1) # basic recurrence
6  else
7    e(m) = -z(m) mod (k-1)
8    if r(m)+e(m)<=0 then e(m) -> e(m)+k-1
9    z(m+1) = z(m) + (z(m) + e(m))/(k-1)
10   r(m+1) = r(m) + e(m)

11 Result for m = M with z(M) <= N < z(M+1):
12 T(N) =r(M) + k(N - z(M))

Definitions: 
    (D1) n is a so-called start number if T(n)<=k-1.
    (D2) z(m) is the sequence of start numbers. 
    (D3) r(m) = T(z(m))

The basic recurrence leads to
    (2a) T(n+1) = T(n)+k       if T(n)+k<=n+1 and
    (2b) T(n+1) = T(n)+k-(n+1) if not

If d(m)=z(m+1)-z(m)>1, a linear progression (difference k) starts with r(m) according to (2a): 
    (3a) T(z(m)+j) = r(m)+j*k, 0<=j<d(m). 
The monotony is broken with j=d(m), according to (2b): 
    (3b) T(z(m)+d(m)) = T(z(m+1))= r(m+1) = r(m)+d(m)*k-z(m+1)
For d(m)=1, (3a) is a tautology and (3b) still holds though there is no progression. d(m)=0 is forbidden. 

Conditions for consecutive start numbers:
   (4a) 1<= r(m) <=k-1, r(m+1)<=k-1, see (D1) 
and, according to (3b):
   (4b) r(m+1) = r(m)+(z(m+1)-z(m))*k-z(m+1), needed for line 10 
After rearrangement:
   (4c) z(m+1) = (k*z(m)+e(m))/(k-1) 
               = z(m) +(z(m)+e(m))/(k-1), see line 9
                 with e(m) = r(m+1)-r(m), see line 10
               
In order to make d(m)=(z(m)+e(m))/(k-1) an integer, we have to postulate:
     (4e) e(m) = q*(k-1)-p(m) 
          with an integer q and p(m) = z(m) mod (k-1)
So we get 
     (4f) r(m+1) = r(m)-p(m)+q*(k-1)
In order to fulfill (4a) we must select 
     (5a) q=0 if r(m)-p(m)> 0 and (5b) q=1 if not
This completes lines 7, 8.

Lines 11, 12:
The recurrence will stop if z(m)<= N < z(m+1). With (3a) and j=N-z(m) we yield the result: 
T(N) = T(z(m)+j) = r(m)+k*(N-z(m))

Lines 1, 3, 4, 5:
As d(m)>=z(m)-z(m) mod(k-1), z(m)>=k-1 is sufficient for d(m)>0. If we fix z(1)=1 as the first start number
and r(1)=T(1)=1, we must use the basic recurrence for z(m)<k-1. This makes the fast recurrence complete.

Exponential increase of z(m):
From (4c) we can see that z(m) increases by an average factor k/(k-1). So the approximate number s of steps
can be taken from (k/(k-1))^s = N: s = log(N)/log(N/(k/(k-1))).