Rewrite k(k-1)/2 - 1 (which must be a power of a prime) as:

(k-2)(k+1)/2

The first or 2nd k-factor is even depending on whether k itself is even.

Suppose k is even, and so k-2 is even and k+1 is odd. Then k/2 - 1 and k + 1 both must be powers of some prime p. k+1 is clearly the larger of the two, so the ratio (k+1)/(k/2 - 1) must be some power of p. It also must be > 1 because k+1 > (k/2 - 1) for all k > 0 and we're given k >= 3. Since the smallest p available is 2, the ratio must be >= 2.

Now for k >= 3, if n > k then (n+1)/(n/2-1) < (k+1)/(k/2-1), and the limit as k goes to infinity is 2. The ratio has a value of 5 when k = 4, 3 when k = 8, and is <3 for k > 8. Since the ratio is also > 2 for all k > 2, the ONLY integral values for the ratio occur for k = 4 and 8. Both of these are indeed solutions, and they are the only ones for even k.

Suppose instead that k is odd. Then k+1 is even and k-2 is odd, and (k+1)/2 and (k-2) must both be powers of the same prime p. They're equal when k = 5, and that's a solution. Otherwise, k-2 is the bigger, so look at the ratio (k-2)/((k+1)/2), which must be a positive power of p. If k > 5 then the ratio is > 1, but it's also < 2 because that's the limit as k goes to infinity. So there are no solutions when k > 5 since there are no primes between 1 and 2. The only other case to consider is k = 3, when the ratio is < 1, and that turns out to be a solution.

So the only odd k solutions are k = 3 and 5, and the only even k solutions are k = 4, 8