practice problems pending

Q1. A sequence has 1st term 2007 and the next term is the sum of the squares of the digits of the previous term. Find the sum of this sequence till 2013 terms.
S1.
Answer: 105336
Once you hit 89, then it will repeat again. So you have to sum that.

Q2.

[Morse–Thue Sequence] Start with 0. To each initial segment append its complement:

0, 01, 0110, 01101001, ...

(a) Let the digits of the sequence be x(0), x(1), x(2) .....

Prove that
x(2n)=x(n)
x(2n+1)=1-x(2n).

(b) Prove that x(n)=1 - x(n - 2^k), where 2^k is the largest power of 2 which is <= n. Find the 1993rd digit of the sequence.

(c) Prove that the sequence is not periodic.

(d) Write the nonnegative integers in base 2:
0,1,10,11...

Now replace each number by the sum of its digits modulo 2. Prove that you obtain the Morse–Thue sequence.

S2.
(a)
We will prove it by strong induction(second principle of induction).
Before that just check for yourself whether it holds for powers of 2. It will clearly.
First we will prove for x(2n) = x(n)
For n = 0
x(0) = x(0) = 0
n=1
x(2) = x(1) = 1

So it proves for n=0,1
Now assume that it's true for all m < n:
x(2m) = x(m)

And using this prove that:
x(2n) = x(n)

Let n = 2^k + y, where 0 <= y < 2^k
It's clear that x(n) = x'(y) = 1- x(n) where x'(y) is complement of x(y).
Why? Since we are simply repeating the earlier bits and taking their complement.

So 2n = 2^(k+1) + 2y and 0<=2y< 2^(k+1) and 2y is even.
=> x(2n) = x'(2y)
And y < n
But we have already assumed that for all m < n the inductive hypothesis holds, i.e.
x(2y) = x(y)
=> x'(2y) = x'(y)
=> x(2n) = x'(2y) = x'(y) = x(n)
H.P.

There is another simple way to see this:
See the sequence:
01,10,1001 ...
Represent the index in binary:
00:0
01:1
10:1
11:0

100:1
101:0
110:0
111:1

So number of 1s in binary representation is even => value = 0
odd => 1
And multiplying a number by 2, i.e. going from n to 2n simply adds a 0 at the end in binary notation.
So the value will remain unchanged.

(a) part 2
Pr. that 
x(2n+1) = 1-x(2n)

But x(2n) = x(n) as we just showed.
Now going from n to 2n retains the value since we are just appending a 0 at the end.
But making it 2n+1 replaces the last 0 with 1.
So it's easy to see that x(2n+1) will be complement of x(n).

Now the inductive proof.

x(2*0 + 1) = x(1) = 1 = 1-x(2*0) = 1-x(0) = 1

x(2*1 + 1) = x(3) = 0 = 1-x(2*1) = 1-x(2) = 1 - x(1) = 0

So it holds for n = 0,1

Inductive hypothesis: x(2m + 1) = 1-x(2m) for all m < n.
Using this pr.th. for 'n'.

Given: x(2m + 1) = 1-x(2m) = 1-x(m)
Let n = 2^k + y where 2^k is the largest power of 2 <= n and 0 <= y < 2^k
=> 2n + 1 =2^(k+1) + 2y + 1
=> 
x(2n+1) = x(2y+1) as we showed earlier.
But since y < n and according to our inductive hypothesis:
x(2y+1) = 1-x(2y) = 1-x(y)
=>
x(2n+1) = 1-x(y)
Also
x(2n) = x(2y) = x(y)
=>
x(2n+1) = 1-x(2n)
H.P.