$3$種類の記号$a,\ b,\ c$から重複を許して$n$個を選び，それらを一列に並べて得られる長さ$n$の記号列を考える．このような記号列のなかで，$a$がちょうど偶数個含まれるようなものの総数を$g(n)$とする．ただし，$0$個の場合も偶数個とみなす．たとえば，$g(1)=2$，$g(2)=5$である．
(1) 自然数$n \geqq 1$に対して$g(n+1)=g(n)+3^n$が成り立つことを示せ．
(2) $g(n)$を求めよ．
(3) 一般に，$a$を含む$m$種類の記号から重複を許して$n$個を選び，それらを一列に並べて得られる長さ$n$の記号列を考える．ただし，$m \geqq 2$とする．このような記号列のなかで，$a$がちょうど奇数個含まれるようなものの総数を$k_m(n)$とする．自然数$n \geqq 1$に対して，$k_m(n)$を求めよ．