3 added 152 characters in body

Edit: On second thought, this is pretty much exactly Anthony's answer, only slightly more explicit. Didn't see this when I wrote this up, sorry.

There's an approach to this problem using elementary linear algebra, which gives you an explicit formula for $f(n)$ each $b$ (however no nice formula for an all $b$ at once), and an algebraic integer $a$ such that $f(n)=c\cdot a^n + \textrm{lower order terms}$. For instance, for $b=3$ you obtain $a = \frac{1+\sqrt{5}}{2}$ and for $b=4$ you obtain $a = \sqrt{3}$. The actual formulas get really messy, for instance for $b=3$ you get (thanks to Maple) $$f(n) = 8/5\cdot {\frac {-120-60\,\sqrt {5}+10\, \left( -1 \right) ^{1+n} \left( \sqrt {5}+1 \right) ^{-n}{2}^{n}+11\, \left( \sqrt {5}+2 \right) ^{n-1 } \left( 3+\sqrt {5} \right) ^{2-n}\sqrt {5}{2}^{n}+5\, \left( -1 \right) ^{n} \left( \sqrt {5}-1 \right) ^{-n+1} \left( 3+\sqrt {5} \right) ^{-n+1}{4}^{n}+ \left( -1 \right) ^{1+n}{2}^{1+n}\sqrt {5} \left( \sqrt {5}+1 \right) ^{-n}+25\, \left( \sqrt {5}+2 \right) ^{n- 1} \left( 3+\sqrt {5} \right) ^{2-n}{2}^{n}}{ \left( \sqrt {5}-1 \right) ^{2} \left( 3+\sqrt {5} \right) ^{2} \left( \sqrt {5}+1 \right) }}$$ the first ten values of which are $3, 7, 13, 23, 39, 65, 107, 175, 285, 463, \ldots$

So, the following is a description of how to obtain the growth behavior and explicit formulas (some details are missing since this got a bit longer than I expected):

First notice that the diagrams that you draw in your question are uniquely determined by the foldable sequence in all except in $b$ cases, namely the sequences $[i,i,\ldots,i]$ for which there are two possible diagrams. To see this just notice that whenever a sequence contains a subsequence [i-1,i] or $[i,i-1]$ this subsequence is represented in the diagram by a blue line crossing the $i$-th vertical red line in your digram, and the rest of the diagram is hence determined (See it this way: whenever you "add a digit" to your sequence this corresponds to a unique extension of the blue line, the only ambiguous part was the placement of the first line segment). In conclusion we focus our interest on the number $g(n)$ of possible "folding diagrams", and we have $$g(n) = f(n) + b$$ (in fact this is where the summand $-2$ comes from in your formula; it will turn out that $g(n)$ is essentially a linear combination of exponential functions)

Now we decompose $$g(n) = g_{0,0}(n) + g_{1,0}(n)+ g_{1,1}(n)+g_{2,1}(n)+g_{2,2}(n) + \ldots + g_{b-1,b-2}(n) + g_{b-1,b-1}(n) + g_{b,b-1}(n)$$ where $g_{i,j}(n)$ denotes the number of all folding diagrams corresponding to a sequence which starts with the digit $j \in \{ 0,\ldots,b-1 \}$ and is rooted at the $i$-th vertical red line in your diagram (counting from the left starting at $0$; so, $j\in \{0,\ldots, b\}$ and for a given $i$ the value of $j$ has to be $i$ or $i-1$).

Now the $g_{i,j}$ satisfy a linear recursive formula (this is obvious: once we specify the first line segment of a folding diagram we can concatenate it with any folding diagram of length $n-1$ which starts at the right vertical red line to obtain a folding diagram of length $n$): $$g_{i,i}(n) = g_{i+1,i}(n-1) + g_{i+1,i+1}(n-1) \quad \textrm{ for } i\in\{0,\ldots,b-2\}$$ $$g_{i,i-1}(n) = g_{i-1,i-1}(n-1) + g_{i-1,i-2}(n-1) \quad \textrm{ for } i\in\{2,\ldots,b\}$$ $$g_{1,0}(n) = g_{0,0}(n-1) \quad \textrm{and} \quad g_{b-1,b-1}(n) = g_{b,b-1}(n-1)$$ Note that by definition $g_{i,j}(1)=1$ for all $g_{i,j}$'s which occur in these recursion relations. So we can put this recursion relation into a matrix $A_b$, and we will get a formula $$\left(\begin{array}{c}g_{0,0}(n)\newline g_{1,0}(n) \newline g_{1,1}(n)\newline \vdots \newline g_{b,b-1}(n) \end{array}\right) = A_b \cdot \left(\begin{array}{c}g_{0,0}(n-1)\newline g_{1,0}(n-1) \newline g_{1,1}(n-1)\newline \vdots \newline g_{b,b-1}(n-1) \end{array}\right) = A_b^{n-1}\cdot \left(\begin{array}{c} 1\newline 1 \newline 1 \newline \vdots \newline 1\end{array}\right)$$ Since $g(n)$ was just the sum of all $g_{i,j}(n)$ and $f(n)=g(n)-2$ we get $$f(n) = [1,\ldots,1]\cdot A_b^{n-1} \cdot [1,\ldots,1]^\top-b$$ It should be clear now that by transforming $A_b$ into Jordan normal form we can get an explicit formula for each $b$ (as a linear combination of $\leq n$-th powers of the eigenvalues of $A_b$).

So when it comes to the growth behavior, we're interested in the eigenvalue of $A_b$ of biggest absolute value. Now the matrices $A_b$ have a very simple form: $$A_3 = \left[ \begin {array}{cccccc} 0&1&1&0&0&0\newline 1&0&0&0 &0&0\newline 0&0&0&1&1&0\newline 0&1&1&0&0&0 \newline 0&0&0&0&0&1\newline 0&0&0&1&1&0 \end {array} \right] \quad A_4 = \left[ \begin {array}{cccccccc} 0&1&1&0&0&0&0&0\newline 1 &0&0&0&0&0&0&0\newline 0&0&0&1&1&0&0&0 \newline 0&1&1&0&0&0&0&0\newline 0&0&0&0&0&1&1 &0\newline 0&0&0&1&1&0&0&0\newline 0&0&0&0&0&0 &0&1\newline 0&0&0&0&0&1&1&0\end {array} \right]$$ Notice how $A_{b}$ sits as a submatrix in the lower right corner of $A_{b+1}$, and this should be suffice to prove the following recurrence relation for the characteristic polynomials $\chi_b(x)$ of $A_b$ (to be honest I just checked it up to $b=10$ but it should be doable): $$\chi_{b+1}(x) = x^2\cdot(\chi_b(x) - \chi_{b-1}(x))$$ Together with the information that $\chi_2(x)=x^2-2$ and $\chi_3(x)=x^4-2x^2$ this gives you all characteristic polynomials for all the $A_b$ fairly easily.

So we get $$f(n) = c \cdot a^n + \textrm{lower order terms}$$ where $a$ is the largest absolute value of a root of $\chi_b(x)$.

A few technicalities are required to make sure that $c\neq 0$: one should only consider roots of $\chi_b(x)$ which aren't multiples of $\sqrt{-1}$ (these will cancel each other out) and secondly, one needs to make sure that the vector $[1,\ldots,1]^\top$ doesn't lie in an $A_b$-stable proper subspace of $\mathbb R^{2b}$ (this can probably be shown, but it's too messy for me right now and I already spent more time on this answer than I should've).

2 inaccuracy in the first version
f(n) = 8/5\cdot {\frac {32}{5}}\cdot{\frac {-20-10\,\sqrt -120-60\,\sqrt {5}+65\,{2}^{n} 5}+10\, \left( 3+\sqrt -1 \right) ^{1+n} \left( \sqrt {5} 5}+1 \right) ^{-n} {-n}{2}^{n}+11\, \left( \sqrt {5}+2 \right) ^{n}+5\, {n-1} \left( 3+\sqrt {5} \right) ^{2-n}\sqrt {5}{2}^{n}+5\, \left( -1 \right) ^{1+n} {n} \left( \sqrt {5}+1 5}-1 \right) ^{-n}{2}^{n}+29\,\sqrt {5}{2}^{n} {-n+1} \left( 3+\sqrt {5} \right) ^{-n} {-n+1}{4}^{n}+ \left( \sqrt {5}+2 -1 \right) ^{n}+\sqrt {1+n}{2}^{1+n}\sqrt {5} \left( \sqrt {5}+1 \right) ^{-n} {-n}+25\, \left( -1 \sqrt {5}+2 \right) ^{n}{2}1} \left( 3+\sqrt {5} \right) ^{n}}{ {2-n}{2}^{n}}{ \left( \sqrt {5}-1the first ten values of which are $8, 143, 7, 2413, 4023, 6639, 10865, 176107, 286175, 464285, 752463, \ldots$

First notice that the diagrams that you draw in your question are uniquely determined by the foldable sequence in all except two in $b$ cases, namely the sequences $[0,0,\ldots,0]$ and $[b-1,b-1,\ldots,b-1]$ [i,i,\ldots,i]$for which there are two possible diagrams. To see this just notice that whenever a sequence contains a subsequence [i-1,i] or$[i,i-1]$this subsequence is represented in the diagram by a blue line crossing the$i$-th vertical red line in your digram, and the rest of the diagram is hence determined (See it this way: whenever you "add a digit" to your sequence this corresponds to a unique extension of the blue line, the only ambiguous part was the placement of the first line segment). In conclusion we focus our interest on the number$g(n)$of possible "folding diagrams", and we have 1 There's an approach to this problem using elementary linear algebra, which gives you an explicit formula for$f(n)$each$b$(however no nice formula for an all$b$at once), and an algebraic integer$a$such that$f(n)=c\cdot a^n + \textrm{lower order terms}$. For instance, for$b=3$you obtain$a = \frac{1+\sqrt{5}}{2}$and for$b=4$you obtain$a = \sqrt{3}$. The actual formulas get really messy, for instance for$b=3$you get (thanks to Maple) $$f(n) = {\frac {32}{5}}\cdot{\frac {-20-10\,\sqrt {5}+65\,{2}^{n} \left( 3+\sqrt {5} \right) ^{-n} \left( \sqrt {5}+2 \right) ^{n}+5\, \left( -1 \right) ^{1+n} \left( \sqrt {5}+1 \right) ^{-n}{2}^{n}+29\,\sqrt {5}{ 2}^{n} \left( 3+\sqrt {5} \right) ^{-n} \left( \sqrt {5}+2 \right) ^{n }+\sqrt {5} \left( \sqrt {5}+1 \right) ^{-n} \left( -1 \right) ^{n}{2} ^{n}}{ \left( \sqrt {5}-1 \right) ^{2} \left( 3+\sqrt {5} \right) ^{2} \left( \sqrt {5}+1 \right) }}$$ the first ten values of which are$8, 14, 24, 40, 66, 108, 176, 286, 464, 752, \ldots$So, the following is a description of how to obtain the growth behavior and explicit formulas (some details are missing since this got a bit longer than I expected): First notice that the diagrams that you draw in your question are uniquely determined by the foldable sequence in all except two cases, namely the sequences$[0,0,\ldots,0]$and$[b-1,b-1,\ldots,b-1]$for which there are two possible diagrams. To see this just notice that whenever a sequence contains a subsequence [i-1,i] or$[i,i-1]$this subsequence is represented in the diagram by a blue line crossing the$i$-th vertical red line in your digram, and the rest of the diagram is hence determined (See it this way: whenever you "add a digit" to your sequence this corresponds to a unique extension of the blue line, the only ambiguous part was the placement of the first line segment). In conclusion we focus our interest on the number$g(n)$of possible "folding diagrams", and we have $$g(n) = f(n) + 2$$ (in fact this is where the summand$-2$comes from in your formula; it will turn out that$g(n)$is essentially a linear combination of exponential functions) Now we decompose $$g(n) = g_{0,0}(n) + g_{1,0}(n)+ g_{1,1}(n)+g_{2,1}(n)+g_{2,2}(n) + \ldots + g_{b-1,b-2}(n) + g_{b-1,b-1}(n) + g_{b,b-1}(n)$$ where$g_{i,j}(n)$denotes the number of all folding diagrams corresponding to a sequence which starts with the digit $j \in \{ 0,\ldots,b-1 \}$ and is rooted at the$i$-th vertical red line in your diagram (counting from the left starting at$0$; so, $j\in \{0,\ldots, b\}$ and for a given$i$the value of$j$has to be$i$or$i-1$). Now the$g_{i,j}$satisfy a linear recursive formula (this is obvious: once we specify the first line segment of a folding diagram we can concatenate it with any folding diagram of length$n-1$which starts at the right vertical red line to obtain a folding diagram of length$n$): $$g_{i,i}(n) = g_{i+1,i}(n-1) + g_{i+1,i+1}(n-1) \quad \textrm{ for } i\in\{0,\ldots,b-2\}$$ $$g_{i,i-1}(n) = g_{i-1,i-1}(n-1) + g_{i-1,i-2}(n-1) \quad \textrm{ for } i\in\{2,\ldots,b\}$$ $$g_{1,0}(n) = g_{0,0}(n-1) \quad \textrm{and} \quad g_{b-1,b-1}(n) = g_{b,b-1}(n-1)$$ Note that by definition$g_{i,j}(1)=1$for all$g_{i,j}$'s which occur in these recursion relations. So we can put this recursion relation into a matrix$A_b$, and we will get a formula $$\left(\begin{array}{c}g_{0,0}(n)\newline g_{1,0}(n) \newline g_{1,1}(n)\newline \vdots \newline g_{b,b-1}(n) \end{array}\right) = A_b \cdot \left(\begin{array}{c}g_{0,0}(n-1)\newline g_{1,0}(n-1) \newline g_{1,1}(n-1)\newline \vdots \newline g_{b,b-1}(n-1) \end{array}\right) = A_b^{n-1}\cdot \left(\begin{array}{c} 1\newline 1 \newline 1 \newline \vdots \newline 1\end{array}\right)$$ Since$g(n)$was just the sum of all$g_{i,j}(n)$and$f(n)=g(n)-2$we get $$f(n) = [1,\ldots,1]\cdot A_b^{n-1} \cdot [1,\ldots,1]^\top-2$$ It should be clear now that by transforming$A_b$into Jordan normal form we can get an explicit formula for each$b$(as a linear combination of$\leq n$-th powers of the eigenvalues of$A_b$). So when it comes to the growth behavior, we're interested in the eigenvalue of$A_b$of biggest absolute value. Now the matrices$A_b$have a very simple form: $$A_3 = \left[ \begin {array}{cccccc} 0&1&1&0&0&0\newline 1&0&0&0 &0&0\newline 0&0&0&1&1&0\newline 0&1&1&0&0&0 \newline 0&0&0&0&0&1\newline 0&0&0&1&1&0 \end {array} \right] \quad A_4 = \left[ \begin {array}{cccccccc} 0&1&1&0&0&0&0&0\newline 1 &0&0&0&0&0&0&0\newline 0&0&0&1&1&0&0&0 \newline 0&1&1&0&0&0&0&0\newline 0&0&0&0&0&1&1 &0\newline 0&0&0&1&1&0&0&0\newline 0&0&0&0&0&0 &0&1\newline 0&0&0&0&0&1&1&0\end {array} \right]$$ Notice how$A_{b}$sits as a submatrix in the lower right corner of$A_{b+1}$, and this should be suffice to prove the following recurrence relation for the characteristic polynomials$\chi_b(x)$of$A_b$(to be honest I just checked it up to$b=10$but it should be doable): $$\chi_{b+1}(x) = x^2\cdot(\chi_b(x) - \chi_{b-1}(x))$$ Together with the information that$\chi_2(x)=x^2-2$and$\chi_3(x)=x^4-2x^2$this gives you all characteristic polynomials for all the$A_b$fairly easily. So we get $$f(n) = c \cdot a^n + \textrm{lower order terms}$$ where$a$is the largest absolute value of a root of$\chi_b(x)$. A few technicalities are required to make sure that$c\neq 0$: one should only consider roots of$\chi_b(x)$which aren't multiples of$\sqrt{-1}$(these will cancel each other out) and secondly, one needs to make sure that the vector$[1,\ldots,1]^\top$doesn't lie in an$A_b$-stable proper subspace of$\mathbb R^{2b}\$ (this can probably be shown, but it's too messy for me right now and I already spent more time on this answer than I should've).