Find the natural number $a$ for which $\sum^n_{k=1}f(a+k)=16(2^n-1)$, given that $f(x+y)=f(x)\,f(y)$.

Question

Find the natural number $a$ for which $$\sum^n_{k=1}f(a+k)=16(2^n-1)\,,$$ where the function $f:\mathbb{N}\to\mathbb{N}$ satisfies the relation $$f(x+y)=f(x)f(y)\text{ for all }x,y\in \mathbb{N}$$ and further $f(1) = 2$.

Please solve this.

Answer 1

The first thing to find is what $f(x)$ is

$$f(1) = 2 = f(1+0) = f(1)*f(0)$$

Therefore, $f(0) = 1$

$$f(2) = f(1)f(1) = 2^2$$ $$f(3) = f(2)f(1) = f(1)f(1)f(1) = 2^3$$

Clearly, $f(x) = 2^x, x \in \mathbb{N}$

Now

$$\sum_{k=1}^n 2^{a+k} = 16(2^n-1)$$ $$2^a\sum_{k=1}^n 2^k = 16(2^n-1)$$ $$2^a \cdot \frac{2^{n+1} - 2}{2-1} = 16(2^n-1)$$ $$2^a(2 \cdot(2^n-1)) = 16(2^n-1)$$ Clearly $a = 3$

Answer 2

Hint: Compare $$16(2^n-1)=\dfrac{16(2^n-1)}{2-1}=16(1+2+2^2+\cdots+2^{n-1})=16\sum_{k=0}^{n-1}2^{k}$$ with $$\sum^n_{k=1}f(a+k)=f(a)\sum_{k=0}^{n-1}f(1+k)$$

Answer 3

By using the functional equation we can simplify the sum as follows

$$\sum_{k=1}^n f(a+k)~=~\sum_{k=1}^n f(a)f(k)~=~f(a)\sum_{k=1}^n f(k)$$

Now it is possible to rewrite the functions $f(a),f(k)$ in terms of powers of $2$

$$f(n)~=~f(1+(n-1))~=~f(1)f(1+(n-2))~=~f(1)f(1)f(1+(n-3))~\cdots~=~f(1)^n$$

where the last term equals the $\text{n}^{th}$ power of $2$. Therefore the sum becomes

$$f(a)\sum_{k=1}^n f(k)~=~2^a\sum_{k=1}^n 2^k~=~2^a[2+2^2+2^3+\cdots+2^{n-1}]~=~2^a~2\cdot\left[\frac{2^{n}-1}{2-1}\right]$$

Simplifing this leads to

$$2^a~2\cdot(2^n-1)~=~16\cdot(2^n-1)~\Leftrightarrow~2^a~=~8$$

and so this yields to $a=3$.

Answer 4

Here is a solution using the generating function technique. Let $g(t)$ be the power series $$g(t):=\sum_{k=1}^\infty\,f(k)\,t^{k-1}\,.$$ Then, $$f(1)\,t\,g(t)=\sum_{k=1}^\infty\,f(1)\,f(k)\,t^{k}=\sum_{k=1}^\infty\,f(k+1)\,t^{k}\,.$$ Let $c:=f(1)$. We get $$c\,t\,g(t)=\sum_{k=0}^\infty\,f(k+1)\,t^k-f(1)=g(t)-f(1)=g(t)-c\,.$$ This shows that $$\big(1-c\,t\big)\,g(t)=c\text{ or }g(t)=\frac{c}{1-c\,t}\,.$$ This shows that $$g(t)=c\,\sum_{k=0}^\infty\,(c\,t)^k=\sum_{k=1}^\infty\,c^k\,t^{k-1}\,.$$ Thus, $f(k)=c^k$ for every $k=1,2,3,\ldots$. The rest is just as other people have answered.