Número esperado de ensayos para obtener N caras consecutivas

Dado un número N. La tarea es encontrar el número esperado de veces que se debe lanzar una moneda para obtener N caras consecutivamente.
Ejemplo: 
 

Entrada: N = 2 
Salida: 6
Entrada: N = 5 
Salida: 62 
 

Planteamiento: 
La clave es observar que si vemos cruz entre cualquier N tirada consecutiva, se rompe la racha de caras continuas y tenemos que volver a empezar de nuevo para N caras consecutivas. 
Sea X el número esperado de intentos para obtener N caras consecutivas. A continuación se muestran los casos posibles: 
 

• Caso 1: Si en la 1ª prueba sale cruz entonces significa que hemos desperdiciado una prueba y tendremos que hacer X pruebas más para obtener N cara consecutiva. La probabilidad de este evento es 1/2 y el número total de intentos necesarios para obtener N cabezas consecutivas es (X + recuento del intento anterior desperdiciado) .
• Caso 2: Si, en el segundo intento , sale cruz, significa que hemos desperdiciado todo nuestro intento anterior y tendremos que hacer X intentos más para obtener N cara consecutiva. La probabilidad de este evento es 1/4 y el número total de intentos necesarios para obtener N lanzamientos consecutivos es (X + número de intentos anteriores desperdiciados).
• Caso 3: Si, en la 3ª prueba , se produce cruz, significa que hemos desperdiciado todas nuestras pruebas anteriores y tendremos que hacer X pruebas más para obtener N. La probabilidad de este evento es 1/8 y el número total de intentos necesarios para obtener N lanzamientos consecutivos es (X + recuento del intento anterior desperdiciado) . Esto continuará hasta que obtengamos N caras consecutivas.
• Caso N: Del mismo modo, si en la N- ésima prueba , se produce una cruz, significa que hemos desperdiciado todas nuestras pruebas anteriores y tendremos que hacer X pruebas más para obtener N. La probabilidad de este evento es 1/2 ^N y el número total de intentos necesarios para obtener N lanzamientos consecutivos es (X + recuento del intento anterior desperdiciado) . 
   

De los casos anteriores, la suma de todas las probabilidades da el recuento de ensayos para N caras consecutivas . Matemáticamente: 
 

X = (1/2)*(X+1) + (1/4)*(X+2) + (1/8)*(X+3)+. . .+(1/2 ^N )*(X+N) + (1/2 ^N )*N 
 

Resolviendo la ecuación anterior para X. Tenemos: 
 

By opening the above expressions and arranging it we have:
X = X(1/2 + 1/4 + 1/8 + . . . . . . 1/2N) 
    + (1/2 + 2/4 + 3/8 . . . . . . . + N/2N 
    + N/2N)

La primera parte de las ecuaciones anteriores forma una progresión geométrica y la segunda parte de las ecuaciones anteriores forma una secuencia geométrica aritmética. Resolviendo las sucesiones anteriores por separado tenemos: 
Para Sucesiones Geométricas: 
 

Suma de la serie GP = 1/2 + 1/4 + 1/8 + . . . . . . 1/2 ^N 
primer término (a) es 1/2 
razón común (r) es 1/2 
último término (n-ésimo término) es 1/2 ^N que también es un * r ^N-1 
Por lo tanto, la suma viene dada por: 
Suma de Serie GP = (1/2)*( (1 – (1/2) ^N )/(1 – 1/2) ) usando la fórmula: (a * (1 – r ^N )) / (1 – r) desde r < 1 
Suma de la serie GP = (1 – (1/2) ^N ) 
 

Para la secuencia geométrica aritmética : 
 

Sea S = Suma de la Secuencia Geométrica Aritmética:
=> S = (1/2 + 2/4 + 3/8 + . . . . . . N/2 ^N ) …….(1)
Multiplicando Por 2, obtenemos 
= > 2S = (1 + 2/2 + 3/4 + . . . . . . . + N/2 ^N-1 ) …….(2)
Restando la ecuación(1) de la ecuación(2), obtenemos 
=> S = (1/2 + 1/4 + 1/8 + . . . . . . 1/2 ^N-1 ) – N/2 ^N 
=> S = suma de la serie GP – N/2 ^N 
=> S = (2 – (1/2) ^N-1 )) – N/2 ^N 
 

Usando la suma de la serie GP y la Secuencia Geométrica Aritmética: 
 

=> X = X*(1 – (1/2) ^N ) + (2 – (1/2) ^N-1 ) – N/2 ^N + N/2 ^N 
=> X = X*(1 – (1 /2) ^N ) + (2 – (1/2) ^N-1 ) 
=> X*((1/2) ^N ) = (2 – (1/2) ^N-1 ) 
=> X = 2 ^{N+ 1} – 2 
 

Ahora, la fórmula anterior para X da el número de intentos que se requieren para obtener N caras consecutivas .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Driver Code
int main()
{
    int N = 3;
 
    // Formula for number of trails for
    // N consecutive heads
    cout << pow(2, N + 1) - 2;
    return 0;
}

// Java implementation of the above approach
class GFG{
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
 
    // Formula for number of trails for
    // N consecutive heads
    System.out.print(Math.pow(2, N + 1) - 2);
}
}
 
// This code is contributed
// by shivanisinghss2110

# Python3 implementation of the above approach
 
# Driver code
if __name__ == '__main__':
     
    N = 3
 
    # Formula for number of trails for
    # N consecutive heads
    print(pow(2, N + 1) - 2)
 
# This code is contributed by mohit kumar 29

// C# implementation of the above approach
using System;
class GFG{
 
// Driver Code
public static void Main()
{
    int N = 3;
 
    // Formula for number of trails for
    // N consecutive heads
    Console.Write(Math.Pow(2, N + 1) - 2);
}
}
 
// This code is contributed
// by Code_Mech

<script>
 
// Javascript implementation of the above approach
 
// Driver Code
     
    let N = 3;
   
    // Formula for number of trails for
    // N consecutive heads
    document.write(Math.pow(2, N + 1) - 2);
       
</script>

14

Complejidad de tiempo: O(1)