It should be T(N) = 2^K * T(N/(2^K)) + 2^(K-1) + 2^(K-2) + ... + 1 = 2^K * T(N/(2^K)) + 2^K - 1. When 2^K = N, this means T(N) = N * T(1) + N - 1 = 2N - 1.I realized that

T(N) = 2^K * T(N/(2^K)) + K should be T(N) = 2^K * T(N/(2^K)) + N

Approach it in the same way: expand the equation several times. I get T(N) = 4^K * T(N/(2^K)) + 4^(K-1) + 4^(K-2) + ... + 1 = (2^K)^2 * T(N/(2^K)) + ((2^K)^2 - 1) / 3.Furthermore, if I have a relation

T(1) = 1

T(N) = 4 * T(N/2) + 1

Any suggestions how to approach this one?

If you need a big-O estimate, see the Master theorem.