No.1
- 回答日時:
実際に具体的な値について計算すればよくわかると思いますよ。
やっていることは、
偶数のときは最下位の桁が0ですから、何もせずに2で割ります。
n=6なら110→11
奇数のときは最下位の桁が1ですから、1引いて2で割ります。
n=3なら11→1
このときにfに1足します。f(n)=f{(n-1)/2} +1←この部分
帰納法での証明ですが、経験者ではないですが参考までに・・・。
桁数がmのときにf(n)がnを2進法で表したときの1の個数を表すと仮定して、残りの上位m-1桁の1の個数がf(n/2)もしくはf{(n-1)/2}で表わせることを示せばよいのではないでしょうか。
No.2
- 回答日時:
二進数では、整数のとき
偶数 → 10010 (一番右のけたが0)
奇数 → 10011 (一番右のけたが1)
となる。また、二進数を2で割るとは、
10010 → 1001
のように、右に一桁シフトすること。
よって、
1)偶数のとき
nを二進数に直したときの1の個数をmとおくと、
(1がm個)0
となるので、2で割ると
(1がm個)
となる。よって、f(n) = f(n/2)である。
2)奇数のとき
nを二進数に直したときの1の個数をmとおくと
(1がm個)1
となるので、n-1は
(1がm個)0
となる。よってこれを2で割ると
(1がm個)
これに1を加える。n=1000101のように、2桁目が0のときはf(n)=100011と なるので一致するが、n=1001111のようになっているとf(n)=101000と なって必ずしも一致しない。f{(n-1)*2}+1とかではないんでしょうか?
No.4ベストアンサー
- 回答日時:
>このときf(n)はnを2進法で表したときの1の個数になると思うのですが、
どこからこの結論が出てきたのかはわかりませんが、正しいです。
>nが偶数のときf(n)=f(n/2)
これは、n=2*m(mは0以上の整数)と考えます。
例えば、m=5であれば、mの2進数表記は101であり、2*mの2進数表記は1010です。
2進数表記でmを2倍するということは、最下位桁に0を追加して元の数を1桁繰り上げるということです。
ですから2倍しても1の個数が変化することはありません。
>nが偶数のときf(n)=f(n/2)
これも、m(mは0以上の整数)を使ってnを書き換えてやれば証明可能なはずです。
tomochan1017さんご自身でトライしてみてください。
No.5
- 回答日時:
一応、f(1)=1 が必要ですが...
で、
条件から、f(2^k)の場合について、f(2^k)=1 がいえるので、
n=2^k の場合は易しいですね。
n=2^k(1)+2^k(2)+.....+2^k(i) のときf(n)=iを証明すればよいので、
n=2^k(1)のとき、f(n)=1 (これは最初に言った)
n=2^k(1)+2^k(2)+.....+2^k(i) のときf(n)=i が成立すれば、
n=2^k(1)+2^k(2)+.....+2^k(i)+2^k(i+1) のときf(n)=i+1
が成立することを示してみれば?
(添え字の数についての帰納法です)
やってみたわけではないので、アイデアのみ。
このとき、k(i)>k(i+1)≧0を仮定しておくと良いでしょう。
2^k(i)についてくくると、末尾に1が現れますので、それを使ってください。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 上三角行列のn乗の証明 2 2023/07/23 21:45
- 数学 以下 n を自然数, p を素数とする. (a) 整数10000を 10000=(a_4)7^4+( 3 2022/05/19 16:54
- 数学 1^2+2^2+…+n^2<(n+1)^3/3を数学的帰納法を用いて証明してください。解法を見てもよ 5 2023/06/14 17:11
- 数学 数学的帰納法の質問です。 n=1、k,k+1のときすべての自然数nが成り立つという証明で、なぜ、n= 7 2023/07/02 11:59
- 数学 全ての自然数nに対して「2^3n−3^n」は5の倍数であることを数学的帰納法で証明 写真の解法は合っ 2 2023/06/18 00:30
- 数学 帰納法 2 2022/06/08 22:25
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- 数学 帰納法 3 2022/06/08 22:24
- 数学 数学の解法について こんばんは。最近数学の問題を解いています。証明問題を解いたのですが、解答とアプロ 4 2022/09/11 23:22
- 数学 √nが有理数ならばnが整数 証明 なぜ √nが有理数ならばnが整数の証明の解答です。わからない部分が 2 2022/08/04 09:41
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
証明終了の記号。
-
中心角の定理
-
夫が亡くなった後の義理家族と...
-
よって・ゆえに・したがって・∴...
-
次元定理以外で
-
数学の証明問題で、「証明終了」...
-
元カレと再婚した方ってなかな...
-
なぜ独身だと養子が持てないの...
-
素数の性質
-
つながった2つのリングを外す
-
高校数学の証明について質問で...
-
3,4,7,8を使って10を作る
-
フェルマーの最終定理。 数学者...
-
2のn乗根で、 nを無限大に持っ...
-
47歳、母親の再婚を子供の立場...
-
高一数学 数1 a,bは実数とする...
-
無理数って二乗しても有理数に...
-
数学の最小値問題の証明
-
完全数が連続した自然数の和で...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
3,4,7,8を使って10を作る
-
証明終了の記号。
-
婿養子に入ったのに出て行けと...
-
数学の証明問題で、「証明終了」...
-
「証明証」と「証明書」はどう...
-
素数の積に1を加算すると素数で...
-
夫が亡くなった後の義理家族と...
-
よって・ゆえに・したがって・∴...
-
学割定期を親に買ってきてもら...
-
(4^n)-1が3の倍数であることの...
-
再婚、奨学金
-
素数の性質
-
なぜ独身だと養子が持てないの...
-
元夫が彼女の存在を隠す理由
-
成人した後両親が離婚し別の人...
-
大学の給付型奨学金について 現...
-
直角三角形の性質
-
通学証明書の契印とは
-
無理数って二乗しても有理数に...
おすすめ情報