Mathematical induction

Printable View

May 6th 2009, 03:29 PM
Apprentice123

Mathematical induction

Solve by induction.The recurrence

$S(n) = 1$ , for $n=1$
$S(n) = [S(\frac{n}{2})]+[S(\frac{n}{2})]+1$ , for $n \geq 2$
May 6th 2009, 04:16 PM
Prove It

Quote:

Originally Posted by Apprentice123

Solve by induction.The recurrence

$S(n) = 1$ , for $n=1$

$S(n) = [S(\frac{n}{2})]+[S(\frac{n}{2})]+1$ , for $n \geq 2$

That doesn't make a whole lot of sense...

Is it possible to have $\frac{3}{2}$ terms? Or any non-integer valued term? Because that's what you'd have for any odd n...
May 6th 2009, 05:32 PM
Soroban

Hello, Apprentice123!

I believe you have misplaced the brackets . . .

Quote:

Solve by induction the recurrence:

$S(1) = 1$
$S(n) \:=\:S\bigg(\!\!\left[\tfrac{n}{2}\right]\!\!\bigg) + S\bigg(\!\!\left[\tfrac{n}{2}\right]\!\!\bigg) +1$ . for $n \geq 2$

If I'm right, we have a fascinating "exponential" sequence . . .

. . $\begin{array}{ccc} \text{Group} & & \text{Value} \\ \hline S(1) &=& 1 \\ S(2),S(3) &=& 3 \\ S(4),S(5),S(6),S(7) &=& 7 \\ S(8),S(9),\;\hdots\; S(15) &=& 15 \\ S(16),S(17),\hdots S(31) &=& 31 \\ \vdots & & \vdots \end{array}$

Each group doubles in length.
The $n^{th}$ group has the value: . $2^n-1$

Good luck with the inductive proof . . .

All times are GMT -8. The time now is 01:14 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.