practice problems

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.
Method 1:

Let the sequence at any step be X_{k+1} = X_k.X'_k
Where X'_k is the complement of X_k.

So X_k has indices from 0 to 2^k - 1
And X'_k has indices from 2^k to 2^k + y where 0 <= y <= 2^k - 1
Clearly x(2^k + y) = 1-x(y)

Now
let S(n) = sum of digits in binary 'n'.
let z(n) = S(n) mod 2
So S(2^k + y) = 1 + S(y) since adding 2^k to y simply adds a '1' at the beginning.
=> z(2^k + y) = 1 - z(y)

So x(n) = z(n) and both are same sequences.
We will use this to prove easily that
(a)
x(2n) = x(n) since multiplying by 2 leaves the sum of digits unchanged
And
x(2n+1) = 1-x(2n) since adding 1 in an even number increases the sum by 1.
(b)
we just proved.
1993rd digit = 1992nd index
1992 = 1024 + 512 + 256 + 128 + 64 + 8
=> S(1992) = 6 => x(1992) = 0

(c)
If the sequence x(n) is periodic then there must be a smallest value of the period, let's say p.
Case 1:
'p' is even.
Let p = 2k
x(2n + p) = x(2n) since adding period doesn't change anything.
Also x(2n) = x(n) by even rule.
So x(2n+p) = x(2n+2k) = x(n+k) = x(2n) = x(n)
So we just proved that x(n+k) = x(n) and k = p/2 so 'p' is not the smallest period. Hence contradiction. 
Basically, we can take any even period and prove that p/2 is also a period. So this leads to a contradiction.

Case 2:
p is odd.
p = 2k + 1
x(2n) = x(n) = x(2n + p) = x(2n + 2k + 1) = 1- x(2n + 2k) = 1-x(n+k)
So:
x(n) = 1-x(n+k)
So shifting by k leads to complement.
=> x(n+k) = 1-(n+2k) => x(n) = x(n+2k)
again we found a smaller period.
contradiction.

Now how does the assumption of 'p' being the smallest matter here?
Let's say we don't assume it being the smallest.
Then let's say there is some p = 100 which is the period.
Then as we showed, 50,25 are also periods(case 1).
Then from 25, 24 is also a period(case 2).
Then 12,6,3,2,1,0 are also periods.
But period is supposed be an integer >= 1.
H.P.




(d)
already proved

Method 2:
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.