  Aims. The purpose of this paper is to detect and investigate the nature of
long-term radial velocity (RV) variations of K-type giants and to confirm
planetary companions around the stars.
  Methods. We have conducted two planet search programs by precise RV
measurement using the 1.8 m telescope at Bohyunsan Optical Astronomy
Observatory (BOAO) and the 1.88 m telescope at Okayama Astrophysical
Observatory (OAO). The BOAO program searches for planets around 55 early K
giants. The OAO program is looking for 190 G-K type giants.
  Results. In this paper, we report the detection of long-period RV variations
of three K giant stars, HD 40956, HD 111591, and HD 113996. We investigated the
cause of the observed RV variations and conclude the substellar companions are
most likely the cause of the RV variations. The orbital analyses yield P =
578.6 $\pm$ 3.3 d, $m$ sin $i$ = 2.7 $\pm$ 0.6 $M_{\rm{J}}$, $a$ = 1.4 $\pm$
0.1 AU for HD 40956; P = 1056.4 $\pm$ 14.3 d, $m$ sin $i$ = 4.4 $\pm$ 0.4
$M_{\rm{J}}$, $a$ = 2.5 $\pm$ 0.1 AU for HD 111591; P = 610.2 $\pm$ 3.8 d, $m$
sin $i$ = 6.3 $\pm$ 1.0 $M_{\rm{J}}$, $a$ = 1.6 $\pm$ 0.1 AU for HD 113996.
