Ufyukyu

2 0 $begingroup$ An input is a string of zeros and ones. Write down a row below it using the Pascal triangle rule, where each number is the sum of the two numbers diagonally above it. We are working “modulo $2$ ” so $1 + 1 = 0$ . Repeat until you form a triangle of numbers. Here is an example, where the input is $10111$ . 1----------0----------1---------1---------1 -----1----------1----------0---------0----- ----------0----------1----------0---------- ---------------1----------1---------------- ---------------------0--------------------- The output of this procedure is the string read along the side of the triangle from the bottom to the top right, in that order. In this case the output is $0 1 0 0 1$ . We decide to use a string of length $n$ as input, so there are $2^n$ possible input strings. How many