自分の知識では解けそうにないので誰か下の漸化式を解いて欲しいです。お願いします。 ガウス記号です⤵︎

自分の知識では解けそうにないので誰か下の漸化式を解いて欲しいです。お願いします。
ガウス記号です⤵︎ ︎
f(n)=f(n-3)+[(n/2)]+1 (n=3,4,5,･･･)
f(0)=1,f(1)=1,f(2)=2

質問者からの補足コメント

• これが何回か実験したやつです

  
    補足日時：2024/03/27 20:43

No.1 ベストアンサー 回答者： ありものがたり 回答日時： 2024/03/27 00:09

厄介なのはガウス記号だから、これを式から無くしてしまえばいい。

n が偶数のとき [(n/2)] = n/2,
n が奇数のとき [(n/2)] = (n-1)/2.
同じことは、[(n/2)] = { 2n - 1 + (-1)^n }/4 でも書ける。
f(n) = f(n-3) + { 2n - 1 + (-1)^n }/4 + 1
　　= f(n-3) + (1/2)n + 3/4 + (1/4)(-1)^n.

n^2 - (n-3)^2 = 6n - 9 を使って漸化式右辺の (1/2)n を消すと、
f(n) - (1/12)n^2 = f(n-3) - (1/12)(n-3)^2 + 3/2 + (1/4)(-1)^n.
n - (n-3) = 3 を使って漸化式右辺の 3/2 を消すと、
f(n) - (1/12)n^2 - (1/2)n = f(n-3) - (1/12)(n-3)^2 - (1/2)(n-3) + (1/4)(-1)^n.

g(n) = f(n) - (1/12)n^2 - (1/2)n と置くと
g(n) = g(n-3) + (1/4)(-1)^n.
その解は、
g(0) = f(0) - (1/12)0^2 - (1/2)0 = 1,
g(1) = f(1) - (1/12)1^2 - (1/2)1 = 5/12,
g(2) = f(2) - (1/12)2^2 - (1/2)2 = 2/3,
g(3) = g(0) + (1/4)(-1)^3 = 3/4,
g(4) = g(1) + (1/4)(-1)^4 = 2/3,
g(5) = g(2) + (1/4)(-1)^5 = 7/12,
以下、周期 6 で繰り返す。

この表から n = 0,1,2,3,4,5 に対する g(n) を表す式を何かでっち上げて、
f(n) = (1/12)n^2 + (1/2)n + g(nを6で割った余り) とすればよい。
でっち上げる g(n) の式は、6 個の n であてはまればどんな式でもよい。
例えば、5 次多項式なんか簡単につくれるし、他でもよい。

この回答へのお礼

わお、すげえ。ありがとうございます。

ただ分からないところがあって
＞n^2 - (n-3)^2 = 6n - 9 を使って漸化式右辺の (1/2)n を消すと、
f(n) - (1/12)n^2 = f(n-3) - (1/12)(n-3)^2 + 3/2 + (1/4)(-1)^n.
n - (n-3) = 3 を使って漸化式右辺の 3/2 を消すと、
f(n) - (1/12)n^2 - (1/2)n = f(n-3) - (1/12)(n-3)^2 - (1/2)(n-3) + (1/4)(-1)^n.

ここの操作を詳しく知りたいです。
漸化式を解くときの技術ですか？

お礼日時：2024/03/27 00:41

No.4 回答者： ありものがたり 回答日時： 2024/03/27 14:19

No.1 は、私のやり方のクセなのですが、

No.2 の方向でもっと話を整理する手もあります。

f(n) = f(n-3) + [n/2] + 1 は n が 3 づつ増えてゆく漸化式なので、
f(0) から始まる f(0), f(3), f(6), ... の列と
f(1) から始まる f(1), f(4), f(7), ... の列と
f(2) から始まる f(2), f(5), f(8), ... の列は
それぞれ別個の数列と見ることもできます。

それと、[n/2] の性質が n の偶奇で異なることを合わせると、
f(n) は 6 個の数列
f(6k) = { f(6k-6) + [(6k-3)/2] + 1 } + [6k/2] + 1,
f(6k+1) = { f(6k-5) + [(6k-2)/2] + 1 } + [(6k+1)/2] + 1,
f(6k+2) = { f(6k-4) + [(6k-1)/2] + 1 } + [(6k+2)/2] + 1,
f(6k+3) = { f(6k-3) + [6k/2] + 1 } + [(6k+3)/2] + 1,
f(6k+4) = { f(6k-2) + [(6k+1)/2] + 1 } + [(6k+4)/2] + 1,
f(6k+5) = { f(6k-1) + [(6k+2)/2] + 1 } + [(6k+5)/2] + 1
を混ぜて並べたもととも見れます。

この6本の漸化式は
f(6k) = f(6(k-1)) + 6k,
f(6k+1) = f(6(k-1)+1) + 6k + 1,
f(6k+2) = f(6(k-1)+2) + 6k + 2,
f(6k+3) = f(6(k-1)+3) + 6k + 3,
f(6k+4) = f(6(k-1)+4) + 6k + 4,
f(6k+5) = f(6(k-1)+5) + 6k + 5
と整理できるので、
f(n) = f(n-6) + n　　　←(＊)
とまとめることもできるかな。

あとは、
f(n) = f(n-3) + [n/2] + 1 から
f(3), f(4), f(5) を計算して
(＊） の漸化式を解くだけです。

この回答へのお礼

https://f.yourl.jp/cd9db62e/
1枚目が実験したやつで、2枚目がまとめた表(?)です。

表の左から方法の個数をa(n)個(3つとも同じ数字の時)、b(n)個(2つだけ同じ数字の時)、c(n)個(3つとも同じ数字の時)、合計をf(n)個とします。
f(n)=a(n)+b(n)+c(n)

表からわかる規則性を表すと(証明は自分は分からないので推測)
ⅰ.nが3の倍数の時
a(n)=1,b(n)=[n/2],c(n)=f(n-3)となりそうで、f(n)=f(n-3)+[n/2]+1
ⅱ.nが３の倍数じゃない時
a(n)=0,b(n)=[n/2]+1,c(n)=f(n-3)となりそうで、
f(n)=f(n-3)+[n/2]+1
ⅰ,ⅱからnが3の倍数でもそうじゃなくても結局
f(n)=f(n-3)+[n/2]+1
この漸化式にたどり着きました。

また推測は推測なんですが、実験して出た値をオンライン整数列大辞典で検索してみたら、
https://oeis.org/A001399
と、自分が考えていたのと同じタイトルが出てきてその後の値も推測通りなので正しいのは正しいんだろうと思います。こういうのって証明するとしたら数学的帰納法ですか？そうは思ってもやり方が全然分かりません( ᐛ )

また色々回答ありがとうございます。

お礼日時：2024/03/27 21:30

No.3 回答者： ありものがたり 回答日時： 2024/03/27 13:48

＞ 漸化式を解くときの技術ですか？

受験参考書によく載ってる解法パターンのひとつです。
目的の数列とは別の数列を作って、解ける漸化式へ帰着する
ってやつです。

a(n+1) = p a(n) + q を解くために、これを
a(n+1) + x = p { a(n) + x } に変形して
一旦 a(n) + x を求めるとか、
a(n+1)/p^n = a(n)/p^(n-1) + q/p^n に変形して
a(n)/p^n = a(1)/p^0 + Σ[k=1..n-1] q/p^k で計算するとか、

a(n+2) = p a(n+1) + q a(n) を解くために、これを
a(n+2) + α a(n+1) = β { a(n+1) + α a(n) } に変形して
一旦 a(n+1) + α a(n) を求めるとか、

いろいろありましたよね？

f(n+1) = f(n) + A(n) + B(n) に対して
a(n+1) = a(n) + A(n) となる a(n) を思いつけば、
{ f(n+1) - a(n+1) } = { f(n) - a(n) } + B(n) となって
漸化式が少し簡単にな(る場合があ)ります。

f(n) = f(n-3) + (1/2)n + 3/4 + (1/4)(-1)^n …① と
n^2 = (n-3)^2 + 6n - 9 …② から
① - ②/12 を作れば、
{ f(n) - (1/12)n^2 } = { f(n-3) - (1/12)(n-3)^2 } + 3/2 + (1/4)(-1)^n. …③
更に n - (n-3) = 3 …④ から
③ - ④/2 を作れば、
{ f(n) - (1/12)n^2 - n/2 } = { f(n-3) - (1/12)(n-3)^2 - (n-3)/2 } + (1/4)(-1)^n. …⑤

① を解いて f(n) を求めるよりも
⑤ を解いて f(n) - (1/12)n^2 - n/2 を求めるほうが簡単そうじゃありませんか？

この回答へのお礼

No.3やNo.4、ありがとうございます。まだ漸化式基本的なことしか知らなかったのでそういうやり方があると知れて良かったです。これから学校で習ったりする時意識して色んな解き方を試して視野を広げたいなと思います。

実はこの漸化式、場合の数の問題を解いていた時にそこから気になった、区別のない3つの非負整数の和で非負整数nを表す方法が何通りになるのかを考えていてたどり着いたんです。区別があったらn+2C2で済むんですが区別なしとなると掴みどころがなくて15位まで実験してました。すると規則性っぽいのがあると気づき何とかさっきの漸化式まで行き、そこで詰まったという感じです。その時手書きで表を作ってまとめてたんですが、今手元にないので後でNo.4のお礼に送らせてください。

お礼日時：2024/03/27 14:42

No.2 回答者： ありものがたり 回答日時： 2024/03/27 00:21

あ、g(n) に数式なんかでっちあげなくても、

場合分けで
n ≡ 0 (mod 6) のとき f(n) = (1/12)n^2 + (1/2)n + 1,
n ≡ 1 (mod 6) のとき f(n) = (1/12)n^2 + (1/2)n + 5/12,
n ≡ 2 (mod 6) のとき f(n) = (1/12)n^2 + (1/2)n + 2/3,
n ≡ 3 (mod 6) のとき f(n) = (1/12)n^2 + (1/2)n + 3/4,
n ≡ 4 (mod 6) のとき f(n) = (1/12)n^2 + (1/2)n + 2/3,
n ≡ 5 (mod 6) のとき f(n) = (1/12)n^2 + (1/2)n + 7/12.
とかでもよかったな。