如图，将圆分成n个区域，用3种不同颜色给每一个区域染色，要求相邻区域颜色互异，把不同的染色方法种数记为。求

（1）及与的关系式；
（2）数列的通项公式，并证明：