Totem Poles!

Relevant wiki: Recognizing Recursion

We will create a recursion for the number of totem poles there are of height $n$ . Let $f_n$ denote the number of totem poles possible of height $n$ . Firstly, $f_1 = 1$ and $f_2 = 3$ . We also note that $f_n = f_{n-1} + 2f_{n-2}$ for $n \geq 3$ since totem poles of height $n$ are either a totem pole of height $n-1$ topped with a square-head or a totem pole of height $n-2$ topped with an ash or birch big-head. Thus, it follows:

$\begin{aligned} f_3 &= 3 + 2 \times 1 = 5\\ f_4 &= 5 + 2 \times 3 = 11\\ f_5 &= 11 + 2 \times 5 = 21\\ f_6 &= 21 + 2 \times 11 = 43\\ f_7 &= 43 + 2 \times 21 = 85\\ f_8 &= 85 + 2 \times 43 = 171\\ f_9 &= 171 + 2 \times 85 = 341\\ f_{10} &= 341 + 2 \times 171 = 683\\ f_{11} &= 683 + 2 \times 341 = 1365 \end{aligned}$

Thus, there are $\boxed{1365}$ totem poles of height 11.

Bonus: Prove that the general formula for the totem poles of height $n$ is

$\displaystyle \sum_{k=0}^n (-1)^k 2^{n-k}=\dfrac {2^{n+1}+(-1)^n}{3}$

I think the important thing here is distinguishing that an ash big-head is different than a birch big-head. Originally when I went through this I totally skipped over that piece of information and I was only counting sqaure-heads vs big-heads and got 144 different poles which wasnt correct. But after adjusting to include square-heads, ash big-heads and birch big-heads I got the same answer as Sharky below.

Below is the php I wrote for this

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

<?php  
$t = 0; //total combinations  
$arr = array('p','a','b'); //p = pine square-head (1), a = ash big-head (2), b = birch big-head (2)  
//starting with the 3 above as the base of the totem pole, lets keep adding onto them until we get a height of 11  
do{  
    $newarr = array();  
    foreach($arr as $a){  
        $sum = get_sum($a);  
//if sum is 11, count it then discard it  
        if($sum==11){  
            $t++;  
//if count is less than 11, keep it and add one of each new piece type on top of it  
        } elseif($sum<11){  
            $newarr[] = $a.'p';  
            $newarr[] = $a.'a';  
            $newarr[] = $a.'b';  
        }  
//if count is greater than 11, discard it  
    }  
    $arr = $newarr;  
} while(count($arr));  
//once we've ran through all combinations, print the result  
echo 'total: '.$t; //1365  

//convert letter values to height values and sum them then return the total height  
function get_sum($string){  
    $string = str_replace('p','1',$string);  
    $string = str_replace('a','2',$string);  
    $string = str_replace('b','2',$string);  
    return array_sum(str_split($string));  
}  
?>