# Verifying that the $2n$-th term in a modified generalized Fibonacci sequence of order $n$ is the $n-1$-th Cullen number

I was messing around with recursive sequences and I came across something interesting.

The Fibonacci numbers start with $F_1 = 0$, $F_2=1$, and continues with $F_i = F_{i-1} + F_{i-2}$.

The Tribonacci numbers start with $F_1 = F_2 = 0$, $F_3 = 1$, and continues with $F_i = F_{i-1}+F{i-2}+F{i-3}$

The generalized Fibonacci numbers of order $n$ start with $F_1=F_2=\dots=F_{n-1}=0$, $F_n=1$, and for $i\geq n$, $$F_i=\sum_{j=i-n}^{i-1}F_j.$$

I find the numbers that these generate to be boring, though, so I'm going to invent a new set of sequences called the Gibonacci sequences. The recurrence relation is the same as the Fibonacci sequences, but the initial values are different. For the Gibonacci sequence of order $2$, we have $G_1=G_2=1$ and $G_i = G_{i-1}+G_{i-2}$. Likewise, the generalized Gibonacci numbers of order $n$ we have $G_1=G_2=\dots=G_n=1$ and for $i\geq n$, $$G_i=\sum_{j=i-n}^{i-1}G_j.$$

I'm particularly interested in the point where all the initial values are used up, so to speak -- the last number that is defined in terms of one of the initial values. This would be the $2n$-th term for a Gibonacci sequence of order $n$. For example, when $n=2$, our sequence would be $1,\,1,\,2,\,\boxed{3},\dots$ where the number of interest is highlighted. For $n=3$, our sequence would be $1,\,1,\,1,\,3,\,5,\,\boxed{9},\,\dots$.

What I'm going to do is define a sequence from these numbers as I go up in order for the generalized Gibonacci numbers. We'll define $C_n$ as $G_{2n}$ where $G$ the Gibonacci sequence of order $n$. Our sequence $C$ looks like this:

$$(1,\,3,\,9,\,25,\,65,\,161,\,385,\,\dots).$$

It seems to be the case that the $i$th term in this sequence is precisely $(i-1)\cdot 2^{i-1}+1$. In other words, this sequence seems to generate the Cullen numbers!

I'm very much convinced that this pattern continues for every number in the sequence, but I wouldn't know how to prove this to be the case. That, in essence is my question: how can we prove that this sequence generates the Cullen numbers?

Prove that $G_{n+k}=2^{k-1}(n-1)+1$ for $1\le k\le n$. It's useful to note that $G_{n+k}=2G_{n+k-1}-G_{k-1}$.