Mathings

Primecoins

December 11, 2013

First an introduction, what is Primecoin? According to wikipedia:

Primecoin (sign: Ψ; code: XPM) is a peer-to-peer open source cryptocurrency that implements a scientific computing proof-of-work system.

Primecoin uses the finding of long Cunningham chains for proof-of-work. Cunningham chains are used by cryptosystems, including ElGamal.

Also according to wikipedia:

A Cunningham chain is a certain sequence of prime numbers.

Definition: A Cunningham chain of the first kind (1CC) of length $n$ is a sequence of prime numbers $(p_1, \ldots, p_n)$ such that for all $1 \leq i < n$

$p_{i+1} = 2p_i + 1$

Example: (2, 5, 11, 23, 47) is a 1CC of length 5.

Notice that $11 \neq 2^2 \cdot 2 + 1 = 9$ , but instead $11 = 2(2 \cdot 2 + 1)+1$

Similarly, we define a 2CC

Definition: A Cunningham chain of the second kind (2CC) of length $n$ is a sequence of prime numbers $(p_1, \ldots, p_n)$ such that for all $1 \leq i < n$

$p_{i+1} = 2p_i - 1$

Example: (19, 37, 73) is a 2CC of length 3.

Notice that $73 \neq 2^2 \cdot 19 - 1 = 75$ but instead $73 = 2(2 \cdot 19 - 1) - 1$

This seems to coincide with the primecoin paper, where it says

“A Cunningham chain of the first kind has each prime one more than the double of previous prime in chain, and where Cunningham chain of the second kind has each prime one less than the double of previous prime in chain. A variation of the form is known as bi-twin chain, that is, a chain of twin primes where each twin pair basically doubles the previous twin pair.”

I think my confusion starts with the definition of a bi-twin chain, so I won’t define it. Let’s instead just check the results for the 1CC and the 2CC found by Primecoin.

(*) Edit: At the end of the post everything gets clear.

If I run the following command
listprimerecords 13 2CC

in the Primecoin console, I get as output
[ { "time" : "2013-09-10 22:57:00 UTC", "epoch" : 1378853820, "height" : 159217, "ismine" : false, "primedigit" : 94, "primechain" : "2CC0d.9b948d", "primeorigin" : "2157379196749861922279323942438489646066518556204460081290289105121926523847387648204577131520", "primorialform" : "10756750720700195380397697188448178460115725467111771468875842964723844354555016704*31#" } ]

Notice that what is called “primeorigin” isn’t even a prime number. Let’s call it $p_0$ and think of it as previous to $p_1$ , then, as we are talkin of a 2CC, it should be that
$p_1 = 2 p_0 - 1$
should be a prime number. But it turns out it isn’t.

So let’s think that maybe 1CC and 2CC are interchanged in Primecoin. In that case it should be that
$p_1 = 2 p_0 + 1$
should be a prime number. And it is! Following we should have
$p_2 = 2 p_1 + 1$
should be a prime number. But it isn’t!
I figured out that if instead we make
$p_2 = 2^2 p_0 + 1$
$p_3 = 2^3 p_0 + 1$
…
$p_i = 2^i p_0 + 1$

we get prime numbers for $1 \leq i \leq 12$
(Also, this are only 12 primes, not 13 as I thought I was requesting) (**)

Let’s try another: when I run
listprimerecords 12 2CC
I get (between other results)

{
“time” : “2013-12-05 06:53:58 UTC”,
“epoch” : 1386226438,
“height” : 295139,
“ismine” : false,
“primedigit” : 103,
“primechain” : “2CC0c.a4caf9”,
“primeorigin” : “1285764572562607660402926389038420423264315480012212599885081765424391378752917310800826080871198228480”,
“primorialform” : “98279295935033180629959785897200089181968927279639445372368151461888313357086975983616*43#”
}

Again,
$p_0 = 1285764572562607660402926389038420423264315480012212599885081765424391378752917310800826080871198228480$
isn’t a prime number. And we have

$p_1 = 2 p_0 + 1$
$p_2 = 2^2 p_0 + 1$
$p_i = 2^i p_0 + 1$

all prime for $1 \leq i \leq 11$
(Also, this are only 11 primes, not 12 as I thought I was requesting) (**)

Here I will make a definition

Definition: A Primecoin chain of the first kind (1PC) of length $n$ is a sequence of prime numbers $(p_1, \ldots, p_n)$ such that for all $1 \leq i \leq n$

$p_{i} = 2^i p_0 + 1$

for some $p_0 \in \mathbb{N}$

Example: (19, 37, 73) is a 1PC of length 3, with $p_0 = 9$

So it looks like the implementation of Primecoin is mixing a 2CC with a 1PC.

Let’s see what happens with 1CC
listprimerecords 11 1CC
I get (between other results)

{
“time” : “2013-08-03 18:44:12 UTC”,
“epoch” : 1375555452,
“height” : 95569,
“ismine” : false,
“primedigit” : 140,
“primechain” : “1CC0b.0ca375”,
“primeorigin” : “16640727253474004586160688087254796287314713234888194836242582373213323826931605469636261216936400592303991475386891804398184601469085345290”,
“primorialform” : “73853903764168979088206401473739410396455001112581722569026969860983656346568919*151#”
}

This one is mentioned in wikipedia. (for $k = 11$ )

Again, “primeorigin” isn’t a prime, let’s call it $p_0$ , and what we really have is

$p_1 = 2 p_0 - 1$
$p_2 = 2^2 p_0 - 1$
$p_i = 2^i p_0 - 1$

All primes for $1 \leq i \leq 10$
(So only 10 primes in total) (**)

Again, I’ll make a definition here

Definition: A Primecoin chain of the second kind (2PC) of length $n$ is a sequence of prime numbers $(p_1, \ldots, p_n)$ such that for all $1 \leq i \leq n$

$p_{i} = 2^i p_0 - 1$

for some $p_0 \in \mathbb{N}$

Example: (11, 23, 47) is a 2PC of length 3, with $p_0 = 6$

So it seems the implementation of Primecoin is mixing a 1CC with a 2PC.

This is the wxMaxima code I used to verify this results

(%i1) n : 2157379196749861922279323942438489646066518556204460081290289105121926523847387648204577131520;
(%i2) primep(n);
(%i3) p0: n;
(%i4) p1: 2*p0-1;
(%i5) primep(p1);
(%i6) p1: 2*p0+1;
(%i7) primep(p1);
(%i8) p2: 2*p1+1;
(%i9) primep(p2);
(%i10) p2: 2^2*p0+1;
(%i11) primep(p2);
(%i12) p12: 2^12*p0+1;
(%i13) primep(p12);
(%i14) p0: 1285764572562607660402926389038420423264315480012212599885081765424391378752917310800826080871198228480;
(%i15) p1: 2*p0+1;
(%i16) primep(p1);
(%i17) p2: 2^2*p0+1;
(%i18) primep(p2);
(%i19) p11: 2^11*p0+1;
(%i20) primep(p11);
(%i21) primep(p0-1);
(%i22) p0: 16640727253474004586160688087254796287314713234888194836242582373213323826931605469636261216936400592303991475386891804398184601469085345290;
(%i23) p1: 2*p0-1;
(%i24) primep(p1);
(%i25) p2: 2^2 * p0 – 1;
(%i26) primep(p2);
(%i27) p10: 2^10 * p0 – 1;
(%i28) primep(p10);

(*) Edit: I think I now understand what’s happening here.
Let’s say we have a 1CC
$p_1 = p_1$
$p_2 = 2p_1 + 1$
$p_3 = 2(2p_1 + 1) + 1 = 4 p_1 + 3$
$p_4 = 2(4 p_1 + 3) + 1 = 8 p_1 + 7$

inductively
$p_k = 2^{k-1} p_1 + 2^{k-1} - 1$

On the other hand, let’s say we have a 2PC
$p_0 = p_0$
$p_1 = 2p_0 - 1$
$p_2 = 2^2 p_0 - 1$

inductively
$p_k = 2^k p_0 - 1$

Both sequences are equal iff

$2^k p_0 = 2^{k-1} p_1 + 2^{k-1}$
$2 p_0 = p_1 + 1$
$p_1 = 2p_0 - 1$

which can be accomplished by taking
$p_0 = (p_1 + 1)/2$

So in some sense, both sequences are equivalent, so that ends the problem.

Similarly a 2CC is equivalent to a 1PC.

(**) Also I understood the “origin” of the chain, and how to correctly calculate the length of the chain. (Extracted from bitcoin magazine):

“For the purposes of Primecoin, the “origin” of a bi-twin chain is defined as the average of the first pair, and for single Cunningham chains the origin is what the average of the first pair would be if the Cunningham chain’s twin also existed”

If you read all this up to down here, and you liked the article, feel free to tip me here (if you didn’t like it or it was all wrong, you can tip too)
Primecoin (XPM) Address: AWCufW28c8AJJzjTs38NWBFZVEkpRm39t4 😉

Posted in Uncategorized | Leave a Comment »

The Mandelbrot Set

October 28, 2012

The Mandelbrot Set ASCII Art

                                                     *
                                                   ****
                                                  ******
                                                   *****
                                              * ********* 
                                         *** ****************
                                           ******************** **
                                        *************************
                                       ****************************
                                     *******************************
                                     ******************************
                        * *****     ********************************
                       ***********  ********************************
                      ************* *******************************
                  ** ************** ******************************
****************************************************************
                  ** ************** ******************************
                      ************* *******************************
                       ***********  ********************************
                        * *****     ********************************
                                     ******************************
                                     *******************************
                                       ****************************
                                        *************************
                                           ******************** **
                                         *** ****************
                                              * ********* 
                                                   *****
                                                  ******
                                                   ****
                                                     *

Posted in Uncategorized | Leave a Comment »

On the rationality of definite integrals

August 31, 2011

Let’s think of this problem, suppose that we know that $\int_0^1 f(x) dx = q \in \mathbb{Q}$ is a rational number, does that imply that $\int_0^1 p(x) f(x) dx$ also is a rational number, where $p(x) \in \mathbb{Q}[x]$ is a polynomial function?

The answer is no, and here is a counterexample
$f(x) = \pi x \sin(\pi x)$
$p(x) = x$

$\int_0^1 f(x) dx = 1$
$\int_0^1 x f(x) dx = 1 - \frac{4}{\pi^2}$

Tags: Counterexample
Posted in Uncategorized | Leave a Comment »

Telescopic operation on any abelian group

June 1, 2011

First recall the telescoping series that says that given a sequence of real numbers $(a_i)_{i \in \mathbb{N}}$ then

$\displaystyle \Sigma_{i=1}^{N} a_{i+1} - a_{i} = a_{N+1} - a_{1}$

denoting $\triangle a_{i} = a_{i+1} - a_{i}$ we have
$\displaystyle \Sigma_{i=1}^{N} \triangle a_{i} = a_{N+1} - a_{1}$

for example, if
$a_n = n^2$
and
$N = 10$
then
$\Sigma_{i=1}^{10} \triangle a_i = \Sigma_{i=1}^{10} (i+1)^2 - (i)^2$
$= (2^2 - 1^2) + (3^2 - 2^2) + \ldots + (11^2 - 10^2) = 11^2 - 1^2$
$= a_{N+1} - a_{1}$

Note that in principle we could have defined the sequence $(a_i)_{i \in I}$ over a finite set $I = \{1,2,\ldots, N+1\} \subset \mathbb{N}$ since we need up to the element $a_{N+1}$ of the sequence when we want to add from $1$ to $N$ .
Anyway for the time we’ll fix $I = \mathbb{N}$ .

Definition.
In parallel with this idea we define the telescopic operation for any sequence $(g_i)_{i \in \mathbb{N}}$ of elements on any abelian group $(G, +)$ , as
$\displaystyle \Sigma_{i=1}^{N} \triangle g_i$
where
$\triangle g_i = g_{i+1} + (- g_i)$

Theorem.
Given a sequence $(g_i)_{i \in \mathbb{N}}$ of elements on some abelian group $(G, +)$ , then the telescopic operation is defined and is equal to
$\displaystyle \Sigma_{i=1}^{N} \triangle g_i = g_{N+1} + (- g_1)$
where
$\triangle g_i = g_{i+1} + (-g_i)$
and
$(- g)$ denotes the inverse of the element $g$ of the group.

Proof.
$\displaystyle \Sigma_{i=1}^{N} g_{i+1} + (- g_i) =$
$= [ g_2 + (- g_1) ] + [ g_3 + (- g_2) ] + \ldots + [ g_{N+1} + (- g_N) ]$
by commutativity
$= [ (- g_1) + g_2 ] + [ (- g_2) + g_3] + \ldots + [ (- g_N) + g_{N+1} ]$
by associative
$= (- g_1) + [g_2 + (- g_2) ] + [ g_3 + (- g_3) ] + \ldots + [ g_N + (- g_N) ] + g_{N+1}$
by property of the inverse
$= (- g_1) + g_{N+1}$
and again by commutativity
$= g_{N+1} + (- g_1)$
wich ends the proof.

Examples:

Let $G = SO(2, \mathbb{R})$ that is matrices that represents rotations in the plane $\mathbb{R}^2$ , and each $A \in SO(2, \mathbb{R})$ is of the form
$A = \begin{pmatrix} \cos(\alpha) & -\sin(\alpha) \\ \sin(\alpha) & \cos(\alpha) \end{pmatrix}$
for some $\alpha \in \mathbb{R}$ .
This is a commutative (abelian) group.

Let $g_i = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}^i$ for any $i \in \mathbb{N}$

The first elementes of this sequence are
$g_1 = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$
$g_2 = \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}$
$g_3 = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$
$g_4 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$
$g_5 = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$

Then
$\triangle g_i = g_{i+1} (g_{i})^{-1}$
the first elements are

$\triangle g_1 = \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}^{-1}$

$\triangle g_2 = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}^{-1}$

$\triangle g_3 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}^{-1}$

Then
$\Pi_{i=1}^{20} \triangle g_i = g_{21} (g_1)^{-1}$
$= \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}^{-1}$
$= \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$
$= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

Another example:

Let $G = Z | 6Z$ the cyclic group of 6 elements.

Let $g_i = i^2 + 1 (mod \ 6)$ for any $i \in \mathbb{N}$

The first elementes of this sequence are
$g_1 = 2$
$g_2 = 5$
$g_3 = 4$
$g_4 = 5$
$g_5 = 2$
$g_6 = 1$
$g_7 = 2 = g_1$

Then
$\triangle g_i = g_{i+1} + ( - g_{i} )$
the first elements are

$\triangle g_1 = g_2 + (- g_1) = 5 + (-2) = 3$
$\triangle g_2 = g_3 + (- g_2) = 4 + (-5) = 5$
$\triangle g_3 = g_4 + (- g_3) = 5 + (-4) = 1$
$\triangle g_4 = g_5 + (- g_4) = 2 + (-5) = 3$
$\triangle g_5 = g_6 + (- g_5) = 1 + (-2) = 5$
$\triangle g_6 = g_7 + (- g_6) = 2 + (-1) = 1$

Then
$\Sigma_{i=1}^{17} \triangle g_i = \triangle g_1 + \triangle g_2 + \ldots + \triangle g_{17}$
by the theorem
$= g_{18} + (- g_1)$
with $g_{18} = g_6 = 1$
$= 1 + (-2) = 5$

Posted in Uncategorized | Leave a Comment »

System of recurrence relations

October 27, 2010

Lets consider the system of recurrence relations
$(x_{0}, y_{0}) = (1,0)$
$(x_{n}, y_{n}) = (x_{n-1}, y_{n-1}) + (-y_{n-1}, x_{n-1})$

we can calculate the first iterations
$(x_{1},y_{1}) = (1,0) + (0,1) = (1,1)$
$(x_{2},y_{2}) = (1,1) + (-1,1) = (0,2)$
$(x_{3},y_{3}) = (0,2) + (-2,0) = (-2,2)$
$(x_{4},y_{4}) = (-2,2) + (-2,-2) = (-4,0)$

That is,

$x_{n} = x_{n-1} - y_{n-1}$
$y_{n} = y_{n-1} + x_{n-1}$

$x_n + y_n = 2 x_{n-1}$
but
$x_{n-1} = y_n - y_{n-1}$
so
$x_n + y_n = 2 \triangle y_n$

$y_n - x_n = 2 y_{n-1}$
but
$y_{n-1} = x_{n-1} - x_n$
$= - \triangle x_n$
so
$y_n - x_n = -2 \triangle x_n$

so
$2y_n = 2\triangle y_n - 2\triangle x_n$
$2x_n = 2\triangle y_n + 2\triangle x_n$

$y_n = \triangle y_n - \triangle x_n$
$x_n = \triangle y_n + \triangle x_n$

$y_n = \triangle y_n - \triangle y_n - \triangle x_n$
$y_n = - \triangle x_n$

$x_n = \triangle y_n - \triangle x_n + \triangle x_n$
$x_n = \triangle y_n$

….

$\triangle x_n = -y_{n}$
$\triangle y_n = x_{n}$

taking the finite difference on the second equation
$\triangle^2 y_n = \triangle x_{n}$
and replacing on the first equation

$\triangle^2 y_n = -y_n$
$\triangle^2 y_n + y_n = 0$

I propose the solution
$y_n = 2^{\phi n}$
$\triangle y_n = 2^{\phi n + \phi} - 2^{\phi n}$
$= (2^{\phi} - 1) 2^{\phi n}$
$\triangle^2 y_n = (2^{\phi} - 1)^2 2^{\phi n}$
replacing on the difference equation
$\triangle^2 y_n + y_n = 0$
$(2^{\phi} - 1)^2 2^{\phi n} + 2^{\phi n} = 0$
$2^{\phi n} ( (2^{\phi} - 1)^2 + 1 ) = 0$

If $\alpha = 2^{\phi} - 1$ then
$\alpha^2 + 1 = 0$
wich has solutions
$\alpha_1 = i, \alpha_2 = -i$
so,
$\phi_1 = \log_2(i+1), \phi_2 = \log_2(-i+1)$
So, our solution is of the form
$y_n = c_1 2^{\log_2(i+1) n} + c_2 2^{\log_2(-i+1) n}$

$y_n = c_1 (i+1)^n + c_2 (-i+1)^n$

using the initial conditions
$y_{0}=0, y_{1} =1$
$0 = c_1 + c_2$
$1 = c_1(i+1) + c_2 (-i+1)$

so,
$1 = c_1(i+1) - c_1 (-i+1)$
$= c_1(i+1 - (-i+1))$
$= c_1(i+1+i-1)$
$= c_1(2i)$
$c_1 = \frac{-i}{2}$
$c_2 = \frac{i}{2}$

finally
$y_{n} = \frac{-i}{2} (i+1)^n + \frac{i}{2} (-i+1)^{n} \ \ \ \Box$

and because
$\triangle y_n = x_{n}$
and
$\triangle y_n = \frac{-i}{2} (i+1)^{n+1} + \frac{i}{2} (-i+1)^{n+1} - (\frac{-i}{2} (i+1)^n + \frac{i}{2} (-i+1)^{n})$
$= \frac{-i}{2}(i+1)^n (i+1) + \frac{i}{2}(-i+1)^n (-i+1) - \frac{-i}{2} (i+1)^n - \frac{i}{2} (-i+1)^n$
$= \frac{-i}{2}(i+1)^n (i+1 - 1) + \frac{i}{2}(-i+1)^n(-i+1-1)$

$x_n = \frac{1}{2}(i+1)^n + \frac{1}{2}(-i+1)^n$

so, finally we have

$x_n = \frac{1}{2}(i+1)^n + \frac{1}{2}(-i+1)^n$
$y_n = \frac{-i}{2} (i+1)^n + \frac{i}{2} (-i+1)^{n}$

$(x_n,y_n) = \left( \frac{1}{2}(i+1)^n + \frac{1}{2}(-i+1)^n, \frac{-i}{2} (i+1)^n + \frac{i}{2} (-i+1)^{n} \right) \ \ \ \Box$

$(x_n,y_n) = \frac{1}{2} \left((i+1)^n + (-i+1)^n, i(i+1)^n + i(-i+1)^{n} \right) \ \ \ \Box$

we verify the first values

$(x_0,y_0) = (1,0)$
$(x_1,y_1) = (1,1)$
$(x_2,y_2) = (0,2)$
$(x_3,y_3) = (-2,2)$
$(x_4,y_4) = (-4,0)$
$(x_5,y_5) = (-4,-4)$
$(x_6,y_6) = (0,-8)$

Moreover, we can write the Fibonacci recurrence relation
$F_0=0, F_1=1$
$F_{n+2} = F_{n+1} + F_{n}$
(that has the associated difference equation)
$\triangle^2 F_n + \triangle F_n - F_n = 0$

as a system of recurrence relations.

Calling
$f_n = F_{n}$
$g_n = \triangle F_n$

taking the finite difference
$\triangle f_n = \triangle F_n = g_n$
$\triangle g_n = \triangle^2 F_n$
$= F_n - \triangle F_n$
$= f_n - g_n$

we also transform the initial conditions
$f_0 = 0, g_0 = 1$

so, we are left with the system of difference equations
$f_0 = 0, g_0 = 1$
$\triangle f_n = g_n$
$\triangle g_n = f_n - g_n \ \ \Box$

that equals the system of recurrence relations
$f_0 = 0, g_0 = 1$
$f_{n+1} = f_{n} + g_n$
$g_{n+1} = g_{n} + f_n - g_n$
$= f_n \ \ \Box$

we calculate the first values
$f_0 = 0, g_0 = 1$
$f_1 = 0 + 1 = 1, g_1 = 0$
$f_2 = 1 + 0 = 1, g_2 = 1$
$f_3 = 1+1=2, g_3 = 1$
$f_4 = 2 + 1=3, g_4 = 2$
$f_5 = 3+2=5, g_5 = 3$

where we verify that $f_n = F_n$

We can even write the system of recurrence relations
$f_0 = 0, g_0 = 1$
$f_{n+1} = f_{n} + g_n$
$g_{n+1} = f_n$

in matrix notation

$\begin{pmatrix} f_{n+1} \\ g_{n+1} \end{pmatrix} = \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f_n \\ g_n \end{pmatrix}$

Posted in Uncategorized | Leave a Comment »

Mersenne-like numbers

October 3, 2010

It is known that if $n$ is composite, then $M = 2^n - 1$ is composite.

That is easily proven using the summatory of the exponential function, that is

$\sum_{i=0}^{n-1} a^i = \frac{a^{n}-1}{a-1}$

and so $a-1 | a^n-1$ . With $a=2$ we got

$\sum_{i=0}^{n-1} 2^i = \frac{2^{n}-1}{2-1}$

but if $n= pq$ is composite then $2^{pq} = (2^{p})^q$ so

$\sum_{i=0}^{n-1} 2^i = \frac{(2^{p})^q-1}{2^p-1}$

So $2^p - 1 | 2^n -1$ and it cannot be prime.

We can generalize it to any number of the form

$M_a = (a+1)^n - a^n$ (with $a \in \mathbb{N}$ )

and say that if $n$ is composite, then $M_a$ is also composite $\Box$ .

For example, letting $a=1$ we get the usual mersenne numbers $M_1 = M$ . With $a=2$ we get

$M_2 = 3^n - 2^n$

and every number of the form $M_2$ will be composite if $n$ is composite. If $n=pq$ , then $M_2$ will be a multiple of $3^p-2^p$

We can also generalize the Fermat numbers. First remember that the sum
$\sum_{i=0}^{n-1} a^i b^{n-i} = \frac{a^n - b^n}{a-b}$
implies that $a-b | a^n - b^n$
by letting $c = -b$ in the sum, and if $n$ is odd, we get
$a+c | a^n + c^n$

If $n$ is not a power of 2, then it is a product $n=pq$ with $1 \leq p < n$ and $1 < q \leq n$ and $q$ odd. So $a^n + c^n = (a^p)^q + (c^p)^q$ and
$a^p + c^p | a^n + c^n$

So, the only way a number of the form
$a^n + b^n$
can be prime, is $n$ being a power of two, that is, a number of the form
$a^{(2^m)} + b^{(2^m)}$
for some $m$ natural number.

Even more, noticing that
$M_a = \triangle_a a^n$ (with respect to $a$ )
and that
$\triangle_a a^2 = 2a + 1$
$\triangle_a a^3 = 3a^2 + 3a + 1$
$\triangle_a a^4 = 4a^3 + 6a^2 + 4a + 1$
$\triangle_a a^n = \binom{n}{1} a^{n-1} + \binom{n}{2} a^{n-2} + \ldots + \binom{n}{n-1} a^1 + 1$

we get that $\triangle_a a^n$ will be composite for every $a$ if $n$ is composite $\Box$

For example, if $n = 4 = 2 \cdot 2$ we get
$\triangle_a a^4 = 4a^3 + 6a^2 + 4a + 1$
and it will be composite for every $a$ natural number.

On the other side, for $n=3$ we get
$\triangle_a a^3 = 3a^2 + 3a + 1$
that can be prime for some values of $a$ and composite for other values of $a$ .

Posted in Uncategorized | Leave a Comment »

Exponential series

September 29, 2010

If we want to evaluate the sum

$\sum_{i=0}^n 2^i$

we first find
$\triangle (2^n) = 2^{n+1} - 2^n$
$= 2^n (2-1) = 2^n$
so
$\sum_{i=0}^n 2^i = \left[ 2^n \right]_0^{n+1} = 2^{n+1} - 1 \Box$

Similarly, if we want to evaluate the sum

$\sum_{i=0}^n a^i$

we first find
$\triangle (a^n) = a^{n+1} - a^n$
$= a^n (a-1)$
so
$\sum_{i=0}^n a^i = \left[ \frac{a^n}{a-1} \right]_0^{n+1} = \frac{a^{n+1} - 1}{a-1} \Box$

Similarly, if we want to evaluate the sum

$\sum_{i=0}^n a^i b^i$

we first find
$\triangle (a^n) = a^{n+1}b^{n+1} - a^nb^n$
$= a^nb^n (ab-1)$
so
$\sum_{i=0}^n a^i b^i = \left[ \frac{a^n b^n}{ab-1} \right]_0^{n+1} = \frac{a^{n+1} b^{n+1} - 1}{ab-1} \Box$

Similarly, if we want to evaluate the sum

$\sum_{i=0}^n a^{n-i}$

we first find (taking the difference with respecto to $i$ )
$\triangle (a^{n-i}) = a^{n-i-1} - a^{n-i}$
$= a^{n-i} (\frac{1}{a}-1) = a^{n-i} (\frac{1-a}{a})$
so
$\sum_{i=0}^n a^{n-i} = \frac{a}{1-a} \left[ a^{n-i} \right]_0^{n+1} = \frac{a}{1-a} (a^{-1} - a^n)$
$= \frac{1 - a^{n+1}}{1-a} = \frac{a^{n+1} - 1}{a-1} \Box$

That is, we have
$\sum_{i=0}^n a^i = \sum_{i=0}^{n} a^{n-i}$
which makes sence. For example if $a=2$ and $n=5$ we have
$\sum_{i=0}^{n} a^{n-i} = 2^5 + 2^4 + \ldots + 2^1 + 2^0 = 63 = 2^0 + 2^1 + \ldots + 2^5$

Similarly, if we want to evaluate the sum

$\sum_{i=0}^n a^{i} b^{n-i}$

$a^0b^n + a^1b^{n-1} + \ldots + a^{n-1}b^1 + a^n b^0$

we first find (taking the difference with respecto to $i$ )
$\triangle (a^i b^{n-i}) = a^{i+1}b^{n-i-1} - a^i b^{n-i}$
$= a^i b^{n-i} (\frac{a}{b}-1) = a^i b^{n-i} (\frac{a-b}{b})$
so
$\sum_{i=0}^n a^i b^{n-i} = \frac{b}{a-b} \left[ a^i b^{n-i} \right]_0^{n+1} = \frac{b}{a-b} (a^{n+1}b^{-1} - a^0 b^n)$
$= \frac{a^{n+1} - b^{n+1}}{a-b} \Box$

We can observe a pattern here: if we want to evaluate the sum
$\sum_{i=0}^n a^i b^i c^i d^{n-i} e^{n-i}$
it will surely be of the form
$\frac{a^{n+1}b^{n+1}c^{n+1} - d^{n+1}e^{n+1}}{abc-de}$
and can be proved in a similar way.

Posted in Uncategorized | 1 Comment »

Arithmetic and geometric progressions

September 27, 2010

An arithmetic progression is a secuence of numbers such that two successive numbers differ on a specified constant. If we call $c_1$ to the first number of the secuence, and $d$ to the constant, then

$a_1 = c_1$
$a_{n+1} = a_{n} + d$

So
$\triangle(a_n)+a_n = a_n + d$
$\triangle(a_n) = d$

$a_n = d n + c$

Because $a_1 = c_1$ then $a_1 = d + c = c_1$ and $c = c_1 - d$ , so we have

$a_n = d n + c_1 - d$

$a_n = c_1 + d (n-1) \Box$

And the sum of the arithmetic progression, called the arithmetic series, is

$S_m = \sum_{n=1}^{m} a_n = c_1 n + d \frac{(n-1)n}{2}$
$= \frac{1}{2}(2c_1 n + d(n-1)n)$
$= \frac{n}{2}(c_1 + c_1 + d(n-1))$
$= \frac{n}{2}(c_1 + a_n) \Box$

Instead, a geometric progression is a secuence of numbers such that each number (after the first) is obtained by multiplying the previous one by a fixed non-zero constant called the common-ratio.
If we call $a$ to the first number, and $r$ to the common-ratio then we have

$a_1 = a$
$a_{n+1} = r a_n$

So
$\triangle(a_n) + a_n = r a_n$

$\triangle(a_n) = r a_n - a_n$

$\triangle(a_n) = a_n(r-1)$

I propose as the solution $a_n = c 2^{\alpha n}$
$\triangle(a_n) = c (2^{\alpha n + \alpha} - 2^{ \alpha n})$
$= c 2^{\alpha n}(2^\alpha - 1)$

Then,

$c 2^{\alpha n}(2^\alpha - 1) = c 2^{\alpha n} (r-1)$

$2^\alpha - 1 = r-1$

$2^\alpha = r$

$\alpha = \log_2(r)$

So, the solution was

$a_n = c 2^{\log_2(r) n}$

$a_n = c r^n$

Using the initial condition $a_1 = a$ we have

$a_1 = a = c r$ so $c = a/r$ , finally

$a_n = a r^{n-1} \Box$

And the sum of the geometric progression, called the geometric series, is

$Q_m = \sum_{n=1}^m a_n$

We know that

$\triangle (a_n) = a r^n - a r^{n-1}$
$= ar^{n-1} (r-1)$

If we have

$T_n = \frac{ar^{n-1}}{r-1}$

then

$\triangle(T_n) = \frac{ar^{n}}{r-1} - \frac{ar^{n-1}}{r-1}$

$= \frac{ar^{n-1}r}{r-1} - \frac{ar^{n-1}}{r-1}$
$= \frac{ar^{n-1}}{r-1} (r-1)$
$= ar^{n-1}$

$Q_m = \sum_{n=1}^m ar^{n-1} = \left[ \frac{ar^{n-1}}{r-1} \right]_1^{m+1} = \frac{ar^{m}}{r-1} - \frac{a}{r-1}$

(Note that we evaluate to $m+1$ instead of $m$ in order to include the last summand, for example if $m=1$ then we the total sum equals $a_1$ instead of $0$ ). So,

$= \frac{ar^{m} - a}{r-1}$

$= \frac{a(r^{m} - 1)}{r-1} \Box$

Posted in Uncategorized | Leave a Comment »

Euler Formula and recurrence relation

September 13, 2010

If we define the recurrence relation
$c_0 = 1$
$c_1 = 0$
$c_2 = -1$
$c_3 = 0$
$c_{n+4} = c_{n}$

Then we have the asociated difference equation
$\triangle^4 c_n + 4 \triangle^3 c_n + 6 \triangle^2 c_n + 4 \triangle c_n + c_n = c_n$
$\triangle^4 c_n + 4 \triangle^3 c_n + 6 \triangle^2 c_n + 4 \triangle = 0$
With the initial conditions:
$c(0) = 1$
$\triangle c(0) = c(1)-c(0) = -1$
$\triangle c(1) = -1$
$\triangle c(2) = 1$
$\triangle c(3) = 1$
$\triangle^2 c(0) = \triangle c(1) - \triangle c(0) = 0$
$\triangle^2 c(1) = 2$
$\triangle^2 c(2) = 0$
$\triangle^3 c(0) = \triangle^2 c(1) - \triangle^2 c(0) = 2$
$\triangle^3 c(1) = -2$
$\triangle^4 c(0) = \triangle^3 c(1) - \triangle^3 c(0) = -4$

I propose the solution
$c_n = 2^{\alpha n}$
$\triangle c_n = (2^{\alpha} - 1) 2^{\alpha n}$
$\triangle^2 c_n = (2^{\alpha} - 1)^2 2^{\alpha n}$
$\triangle^3 c_n = (2^{\alpha} - 1)^3 2^{\alpha n}$
$\triangle^4 c_n = (2^{\alpha} - 1)^4 2^{\alpha n}$

So, replacing in the difference equation
$2^{\alpha n} ((2^{\alpha} - 1)^4 + 4 (2^{\alpha} - 1)^3 + 6(2^{\alpha} - 1)^2 + 4(2^{\alpha} - 1)) = 0$

Calling $\beta = 2^{\alpha} - 1$ , we have to solve
$\beta^4 + 4 \beta^3 + 6 \beta^2 + 4 \beta = 0$
Wich has roots
$\beta_{1,2,3,4} = 0,-2, -1+i, -1-i$
So
$\alpha_{1,2,3,4} = \ln_2(1), \ln_2(-1), \ln_2(i), \ln_2(-i)$
So,
$c_n = k_1 \cdot 1^n + k_2 \cdot (-1)^n + k_3 i^n + k_4 (-i)^n$

Using the initial conditions
$1 = k_1 + k_2 + k_3 + k_4$
$0 = k_1 - k_2 + k_3 i - k_4 i$
$-1 = k_1 + k_2 - k_3 - k_4$
$0 = k_1 - k_2 - k_3 i + k_4 i$

Solving this system of linear equations we get
$k_1=k_2 = 0$
$k_3=k_4 = \frac{1}{2}$

So, finally:
$c_n = \frac{i^n + (-i)^n}{2}$

If instead, we define the following recurrence relation
$s_0 = 0$
$s_1 = 1$
$s_2 = 0$
$s_3 = -1$
$s_{n+4} = s_{n}$

It satisfies the same difference equation, so has the same kind of solution
$s_n = k_1 \cdot 1^n + k_2 \cdot (-1)^n + k_3 i^n + k_4 (-i)^n$

Using the initial conditions
$0 = k_1 + k_2 + k_3 + k_4$
$1 = k_1 - k_2 + k_3 i - k_4 i$
$0 = k_1 + k_2 - k_3 - k_4$
$-1 = k_1 - k_2 - k_3 i + k_4 i$

Wich has solutions
$k_1 = k_2=0$
$k_3 = \frac{-i}{2}$
$k_4 = \frac{i}{2}$

So, finally:
$s_n = \frac{(-i) i^n + i (-i)^n}{2}$

If instead we consider the recurrence relation
$e_0 = 1$
$e_1 = i$
$e_2 = -1$
$e_3 = -i$
$e_{n+4} = e_n$

It satisfies the same difference equation, so has the same kind of solution
$e_n = k_1 \cdot 1^n + k_2 \cdot (-1)^n + k_3 i^n + k_4 (-i)^n$

Using the initial conditions
$1 = k_1 + k_2 + k_3 + k_4$
$i = k_1 - k_2 + k_3 i - k_4 i$
$-1 = k_1 + k_2 - k_3 - k_4$
$-i = k_1 - k_2 - k_3 i + k_4 i$

Wich has solutions
$k_1 = k_2=k_4 = 0$
$k_3 = 1$

So, finally:
$e_n = i^n$

It is easy to verify that
$e_n = c_n + i s_n$

Or in other words
$i^n = \frac{i^n + (-i)^n}{2} + i \cdot \frac{(-i) i^n + i (-i)^n}{2}$

that is somewhat similar to Euler’s Formula. (It’s somewhat the special case for $x=0,\pi/2, \pi, 3\pi/4$ )

Edit: (15/9/2010)
Knowing that
$c_n = \frac{i^n + (-i)^n}{2}$
$s_n = \frac{(-i) i^n + i (-i)^n}{2}$
Let’s consider:
$(c_n + i s_n)^2 = (c_n + i s_n)(c_n + i s_n)$
$= c_n^2 + 2ic_ns_n - s_n^2$
$= c_n^2 - s_n^2 + i 2c_n s_n$
$= \frac{((i^n) + (-i)^n)^2}{4} - \frac{((-i)i^n + i(-i)^n)^2}{4} + i2 \frac{i^n + (-i)^n}{2} \frac{(-i) i^n + i (-i)^n}{2}$
$= \frac{((i^n) + (-i)^n)^2 - ((-i)i^n + i(-i)^n)^2}{4} + i \frac{(i^n + (-i)^n)((-i) i^n + i (-i)^n)}{2}$
$= \frac{(i^{2n} + 2i^n(-i)^n + (-i)^{2n}) - (-1i^{2n} + 2i^n(-i)^n - (-i)^{2n})}{4} + i \frac{i^n(-i)i^n + i^ni(-i)^n + (-i)^n(-i)i^n + (-i)^ni(-i)^n}{2}$
$= \frac{(i^{2n} + (-i)^{2n} + i^{2n} + (-i)^{2n})}{4} + i \frac{(-i)i^{2n} + i(-i)^{2n}}{2}$
$= \frac{(i^{2n} + (-i)^{2n})}{2} + i \frac{(-i)i^{2n} + i(-i)^{2n}}{2}$
$= c_{2n} + i s_{2n}$
So it seems to verify a kind of DeMoivre formula.

Posted in Uncategorized | Leave a Comment »

Difference equation vs Recurrence relation

September 6, 2010

There is a close relationship between recurrence relation and difference equation.

Take for example the Fibonacci numbers whose sequence can be defined by the recurrence relation:
$F_0 = 0$
$F_1 = 1$
$F_{n+2} = F_{n+1} + F_{n}$

The firsts terms of this sequence are:
$0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$

Let’s try to write it as a difference equation, we have:
$\triangle( a_n ) = a_{n+1} - a_{n}$
$\triangle^2(a_n) = a_{n+2} - 2a_{n+1} + a_{n}$

From the first equation
$a_{n+1} = \triangle(a_n) + a_n$
And from the second equation
$a_{n+2} = \triangle^2(a_n) + 2a_{n+1} - a_{n}$
$a_{n+2} = \triangle^2(a_n) + 2(\triangle(a_n) + a_n) - a_{n}$
$a_{n+2} = \triangle^2(a_n) + 2\triangle(a_n) + 2a_n - a_{n}$
$a_{n+2} = \triangle^2(a_n) + 2\triangle(a_n) + a_n$

Putting it all together to get the recurrence relation as a difference equation
$\triangle^2(a_n) + 2\triangle(a_n) + a_{n} = \triangle(a_n) + a_n + a_n$
$\triangle^2(a_n) + \triangle(a_n) - a_n = 0$

Let’s verify the solution:
$a_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$
where $\phi$ is the golden ratio.

We have
$\triangle (a_n) = \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\sqrt{5}} - \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$
and
$\triangle^2 (a_n) = \frac{\phi^{n+2} - (1-\phi)^{n+2}}{\sqrt{5}} - 2 \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\sqrt{5}} + \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$

Replacing on the difference equation we have
$\frac{\phi^{n+2} - (1-\phi)^{n+2}}{\sqrt{5}} - 2 \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\sqrt{5}} + \frac{\phi^n - (1-\phi)^n}{\sqrt{5}} + \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\sqrt{5}} - \frac{\phi^n - (1-\phi)^n}{\sqrt{5}} - \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$
$= \frac{\phi^{n+2} - (1-\phi)^{n+2}}{\sqrt{5}} - \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\sqrt{5}} - \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$
$= \frac{\phi^{n+2} - (1-\phi)^{n+2} - \phi^{n+1} + (1-\phi)^{n+1} - \phi^n + (1-\phi)^n}{\sqrt{5}}$
$= \ldots = 0$
that verifies the relation.

Let’s try to find the formula that relates a general linear recurrence relation of the form
$\alpha a_{n+2} + \beta a_{n+1} + \gamma a_n = 0$
with a difference equation of the form
$a \triangle^2(a_n) + b \triangle(a_n) + c (a_n) = 0$

replacing the known fórmulas on the first equation:

$\alpha (\triangle^2(a_n) + 2 \triangle(a_n) + a_n) + \beta (\triangle(a_n) + a_n) + \gamma a_n = 0$
$\alpha \triangle^2(a_n) + 2\alpha \triangle(a_n) + \alpha a_n + \beta \triangle(a_n) + \beta a_n + \gamma a_n = 0$
$\alpha \triangle^2(a_n) + (2\alpha+\beta) \triangle(a_n) + (\alpha + \beta + \gamma) a_n = 0$
So,
$a = \alpha$
$b = 2 \alpha + \beta$
$c = \alpha + \beta + \gamma$
And it’s inverse is
$\alpha = a$
$\beta = b - 2a$
$\gamma = c -b +2a - a = c-b+a$

Let’s try to find the analogous of $e^x$ from differential equations in difference equations, that is we want a function such that
$\triangle(a_n) = a_n$
that is
$a_{n+1} - a_n = a_n$
$a_{n+1} = 2a_n$
if we let $a_0 = 1$ then we have
$a_1 = 2$
$a_2 = 4$
$a_3 = 8$ , etc
we conjecture $a_n = 2^n$
If we want a function such that
$(a_n)' = a_n$ in base $h$ then we have
$\frac{a_{n+h} - a_n}{h} = a_n$
$a_{n+h} = ha_n + a_n$
$a_{n+h} = a_n(1+h)$
for example with $h=2$ we have
$a_0=1$
$a_2=3$
$a_4=9$ , etc
we conjecture $a_n = 3^{n/2}$
and in general we conjecture (in base $h$ )
$a_n = \left( (1+h)^{1/h} \right)^n$
in particular, letting $h \to 0$ we have the traditional
$a_n = e^n$

We can define $e_h = (1 + h)^{1/h}$ , so that $e_1 = 2$ , $e_2 = \sqrt{3}$ , and taking $h \to 0$ we have the traditional $e_0 = e$
With that definition, we have that on base $h$ the function whose derivative is itself is $(e_h)^n$ , so if
$(a_n)' = a_n$
then
$a_n = (e_h)^n$
$=2^n$ (in base 1)

Similarly, we can define $\pi_h$ as half the length of the unitary circle (base $h$ ), and define the unitary circle (base $h$ ) as the unitary regular polygon of $\frac{6}{h}$ sides.
So using the known formula of the aproximation of the length of the circle by inscribed regular polygon, that for the unitary circle is $n \sqrt{2-2\cos(2\pi/n)}$ where $n$ is the number of sides, so in general in base $h$ we have
That $2 \pi_h = \frac{6}{h} \sqrt{2-2\cos(\pi h/3)}$ is the length of a regular polygon of $n=6/h$ sides
In particular,
If $h=1$ then $2 \pi_1 = 6 \sqrt{2-2\cos(\pi 1/3)} = 6$ (length of the hexagon), so $\pi_1 = 3$
If $h=2$ then $2 \pi_2 = 3 \sqrt{2-2\cos(\pi 2/3)} = 3\sqrt{3}$ , so $\pi_2 = 3\sqrt{3}/2$
If $h=3$ then $2 \pi_3 = 2 \sqrt{2-2\cos(\pi)} = 4$ so $\pi_3 = 2$
If $h\to 0$ then $2 \pi_0 = \lim_{h\to 0} \frac{6}{h} \sqrt{2-2\cos(\pi h/3)} = 2\pi$ (the length of the traditional unitary circle), so $\pi_0 = \pi$

If we have a general difference equation of the kind
$(a_n)' + P(n) a_n + Q(n) = 0$
we can think of the solution as
$a_n = u_n \cdot v_n$
so
$(a_n)' = ()$
Finish this kind of first order ode difference equation
$\ldots$

Returning to the relation between difference equation and recurrence relation, a general linear recurrence relation of the form
$\alpha_0 a_{n} + \alpha_1 a_{n-1} + \ldots + \alpha_{k} a_{n+k} = 0$
can be written as a difference equation, considering:
$a_n = a_n$
$\triangle(a_n) = a_{n+1}-a_n$
$\triangle^2(a_n) = a_{n+2}-2a_{n+1}+a_n$
$\triangle^3(a_n) = a_{n+3}-3a_{n+2}+3a_{n+1}-a_n$

$a_{n+1} = \triangle(a_n)+a_n$
$a_{n+2} = \triangle^2(a_n) + 2(a_{n+1}) - a_n$
$= \triangle^2(a_n) + 2\triangle(a_n)+2a_n - a_n$
$= \triangle^2(a_n) + 2\triangle(a_n) + a_n$
$a_{n+3} = \triangle^3(a_n) +3(a_{n+2}) - 3a_{n+1} + a_n$
$= \triangle^3(a_n) + 3(\triangle^2(a_n) + 2\triangle(a_n) + a_n) - 3(\triangle(a_n)+a_n) + a_n$
$= \triangle^3(a_n) + 3\triangle^2(a_n) + 6\triangle(a_n) + 3a_n - 3\triangle(a_n)-3a_n + a_n$
$= \triangle^3(a_n) + 3\triangle^2(a_n) + 3\triangle(a_n) + a_n$

In base $h$
$a_n = a_n$
$h(a_n)' = a_{n+h} - a_n$
$h^2 (a_n)'' = a_{n+2h} - 2a_{n+h} + a_n$

$a_{n+h} = h(a_n)' + a_n$
$a_{n+2h} = h^2 (a_n)'' + 2 a_{n+h} - a_n$
$= h^2 (a_n)'' + 2h (a_n)' + 2a_n - a_n$
$= h^2 (a_n)'' + 2h (a_n)' + a_n$

So, in general
$\triangle^k (a_n) = \sum_{i=0}^k (-1)^{k} \binom{k}{i} a_{n+k-i}$
and
$a_{n+k} = \sum_{i=0}^k \binom{k}{i} \triangle^{k-i}(a_{n})$

Edit: (13/9/2010)
Let’s solve the fibonacci recurrence relation by solving it’s asociated difference equation
$\triangle^2(a_n) + \triangle(a_n) - a_n = 0$
with initial conditions
$F(0) = 0$
$\triangle F(0) = F(1) - F(0) = 1$
I propose the solution
$F(n) = 2^{\phi n}$
$\triangle F(n) = 2^{\phi n + \phi} - 2^{\phi n}$
$= 2^{\phi n}(2^{\phi} - 1)$
$\triangle^2 F(n) = (2^{\phi} - 1)^2 2^{\phi n}$

So, replacing in the difference equation
$(2^{\phi} - 1)^2 2^{\phi n} + (2^{\phi} - 1) 2^{\phi n} - 2^{\phi n} = 0$
$2^{\phi n} [(2^{\phi} - 1)^2 + (2^{\phi} - 1) - 1] = 0$
Calling $\alpha = 2^{\phi} - 1$ we have
$\alpha^2 + \alpha - 1 = 0$
With roots
$\alpha_1 = \frac{-1 + \sqrt{5}}{2}$
$\alpha_2 = \frac{-1 - \sqrt{5}}{2}$
So,
$\phi_1 = \ln_2 (\frac{1+\sqrt{5}}{2})$
$\phi_2 = \ln_2 (\frac{1-\sqrt{5}}{2})$

So, our solution is of the form
$F(n) = c_1 2^{\ln_2 (\frac{1+\sqrt{5}}{2})n} + c_2 2^{\ln_2(\frac{1-\sqrt{5}}{2}) n }$

$F(n) = c_1 (\frac{1+\sqrt{5}}{2})^n + c_2 (\frac{1-\sqrt{5}}{2})^n$

Using the initial conditions
$0 = c_1 + c_2$
$1 = c_1 (\frac{1+\sqrt{5}}{2}) + c_2 (\frac{1-\sqrt{5}}{2})$
So,
$1 = c_1 (\frac{1+\sqrt{5}}{2}) - c_1 (\frac{1-\sqrt{5}}{2})$
$1 = c_1 (\frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2})$
$1 = c_1 \sqrt{5}$
$c_1 = \frac{1}{\sqrt{5}}$
$c_2 = \frac{-1}{\sqrt{5}}$
Finally,
$F(n) = \frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$