Clear[P];
RSolve[{P[k] == 4 P[k - 1] + 1,  P[0] == C}, P[k], 
      k]

Clear[P];
RSolve[{P[k] == 4 P[k - 1] + 1,  P[0] == 1}, P[k], 
      k]