توان های دو که میتوان با آنها اعداد طبیعی را ساخت

Question

اثبات کنید که تمام اعداد طبیعی را میتوان از حاصل جمع توان های دو بدست آورد. میتوان از 2 به توان صفر نیز استفاده کرد.

Answer 1

از استقراء ریاضی استفاده کنید.حک برای $1$ و $1$ درست است:

$1=2^0,2=2^1=2^0+2^0$

فرض کنید که حکم برای $n$ درست باشد یعنی $n= \sum _{k=1}^s2^{t_k}$ بنابر این:

$n+1= \sum _{k=1}^s2^{t_k}+2^0$

یعنی حکم برای $n+1$ نیز درست است لذا حکم برای هر عدد طبیعی درست است.توانها اعداد حسابی اند وگرنه حکم درست نیست مثلن:

$1=2^0,3=2^1+2^0,5=2^1+2^1+2^0=2^2+2^0$

$ \Box $