I was recently working on a piece of software and needed to know the number of different ways that a particular word could be represented in mixed upper-and-lowercase letters. For example, the word "bar"
could be represented as:
{bar, Bar, bAr, baR, BAr, bAR, BaR, BAR}
.
Or, more generally, let 0 = lowercase and 1 = uppercase:
{000, 100, 010, 001, 110, 011, 101, 111}
I did a few of these and figured out that:
f(1) = 2
f(2) = 4
f(3) = 8
f(4) = 16
Which any computer programmer instantly recognizes as f(n) = 2^n
But what if I hadn't been that lucky and my data had resulted in something like:
f(1) = 2
f(2) = 7
f(3) = 24
f(4) = 77
Is there some sort of process that I could use to discover the function?
( Which, in this example, is f(n) = (3^n) - n
)