终于忍不住，还在把这个题转过来，不知有什么规律？

Book1.rar (8.94 KB)

下载次数: 4

2012-10-19 20:57

定义数列｛f(n)｝如下:
f(0)=f(1)=0
f(n)=n－1－f[f(n－1)+1]，n∈N   
  注： （这里中括号就是中括号，没有特殊含义）
求数列｛f(n)｝的通项公式。

列了前100项，没有发现什么规律，不知有没有规律。
把我列的也传上来。

495

定义数列｛f(n)｝如下:
f(0)=f(1)=0
f(n)=n－1－f[f(n－1)+1]，n∈N   
  注： （这里中括号就是中括号，没有特殊含义）
求数列｛f(n)｝的通项公式。

列了前100项，没有发现什么规律，不知有没有规律。 ...
hongxian 发表于 2012-10-19 20:57

先扯两个题外：
1、既然需要说明“中括号就是中括号”，何不干脆不用中括号，全用小括号就行了。这种情况我一般都全用小括号，一来避免误解，二来不必担心括号层数太多。
2、那个是不是要offes2007才能打开啊？我这里打不开……

2# kuing


题目不是我的，是昨天哪个题引出来的YES94的题
excel重新再传一个2003可以打开的。

我用 mathematica 列前100项的结果是：
0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12,
13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23,
24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33,
34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44,
45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 55,
55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61

3# hongxian

噢；
嗯，这个可以打开了，跟我上面列的一样（我没列第0项和第101项）

光看数据，我猜测跟黄金分割有关系，n和f（n）的比似乎越来越接近黄金分割
我用excel算了一下，应该是f(n)=trunc(n*黄金分割)
经过excel验证，前100数据符合楼主给的数据
然后，证明，我不会
如果我没有记错的话，斐波那契数列跟黄金分割有关的，也许跟这个数列有联系，等待牛人

光看数据，我猜测跟黄金分割有关系，n和f（n）的比似乎越来越接近黄金分割
我用excel算了一下，应该是f(n)=trunc(n*黄金分割)
经过excel验证，前100数据符合楼主给的数据
然后，证明，我不会
如果我没有记错的话，斐波那契数列跟黄金分割有关的，也许跟这个数列有联系，等待牛人
joatbmon 发表于 2012-10-19 21:20

的确如此，好观察力
前100项数据都符合 $\left[n\cdot\dfrac{\sqrt5-1}2\right]$
这里的中括号就是高斯函数了，下同。

\[\left[ n\cdot \frac{\sqrt{5}-1}{2} \right]=n-1-\left[ \left( \left[ (n-1)\cdot \frac{\sqrt{5}-1}{2} \right]+1 \right)\cdot \frac{\sqrt{5}-1}{2} \right]\]
这条等式验证了1~10000都成立……

\[\left[ n\cdot \frac{\sqrt{5}-1}{2} \right]=n-1-\left[ \left( \left[ (n-1)\cdot \frac{\sqrt{5}-1}{2} \right]+1 \right)\cdot \frac{\sqrt{5}-1}{2} \right]\]
这条等式验证了1~10000都成立……
kuing 发表于 2012-10-19 21:45

证到了，原来也不是很难。

首先，为方便书写，记黄金分割数为 $\varphi =\bigl(\sqrt{5}-1\bigr)/2$，则 $1/\varphi =\varphi +1$，待证的等式为
\begin{equation}\label{20121019czhjfghds}
[n\varphi ]=n-1-\bigl[ \bigl( [(n-1)\varphi ]+1 \bigr)\varphi \bigr].
\end{equation}

设 $k$ 为任意整数，我们来求一下使 $[n\varphi ]=k$ 成立的所有整数 $n$。由于 $n\varphi $ 不会是整数，所以
\begin{align*}
[ n\varphi ]=k&\iff k<n\varphi <k+1 \\
& \iff k(\varphi +1)<n<(k+1)(\varphi +1) \\
& \iff [k\varphi ]+k+1\leqslant n\leqslant [(k+1)\varphi ]+k+1,
\end{align*}
由于 $0<\varphi <1$，所以，要么 $[(k+1)\varphi ]=[k\varphi ]$，要么 $[(k+1)\varphi ]=[k\varphi ]+1$，因此下面分两类讨论。

（1）当 $[(k+1)\varphi ]=[k\varphi ]$ 时，则 $[n\varphi ]=k$ 的解就只有 $n=[k\varphi ]+k+1$，且 $[(n-1)\varphi ]=k-1$，于是
\[n-1-\bigl[ \bigl( [(n-1)\varphi ]+1 \bigr)\varphi \bigr]=[k\varphi ]+k+1-1-[(k-1+1)\varphi ]=k,\]
所以此时式 \eqref{20121019czhjfghds} 成立；

（2）当 $[(k+1)\varphi ]=[k\varphi ]+1$ 时，则 $[n\varphi ]=k$ 的解就是 $n=[k\varphi ]+k+1$ 和 $n=[k\varphi ]+k+2$，因此下面再分两小类讨论。

    （2-1）当 $n=[k\varphi ]+k+1$ 时，与情况（1）相同，式 \eqref{20121019czhjfghds} 成立；

    （2-2）当 $n=[k\varphi ]+k+2$ 时，则 $[(n-1)\varphi ]=[n\varphi ]=k$，于是
\begin{align*}
n-1-\bigl[ \bigl( [(n-1)\varphi ]+1 \bigr)\varphi \bigr]&=[k\varphi ]+k+2-1-[(k+1)\varphi] \\
& =[k\varphi ]+k+1-([k\varphi ]+1) \\
& =k,
\end{align*}
所以此时式 \eqref{20121019czhjfghds} 也成立。

综上所述，由 $k$ 的任意性，可知式 \eqref{20121019czhjfghds} 对任意整数都成立，得证。

$f(0)=f(1)=0$, $f(n)=n-1-f\bigl(f(n-1)+1\bigr)$, $n\in \mbb N$，求 $f(n)$。

下面利用式 \eqref{20121019czhjfghds} 及第二数学归纳法来证明 $f(n)=[n\varphi ]$, $n\in \mbb N$。

当 $n=0$, $1$ 时显然成立，设 $k$ 正整数，假设 $0\leqslant n\leqslant k$ 时有 $f(n)=[n\varphi ]$，则当 $n=k+1$ 时
\[f(k+1)=k-f\bigl(f(k)+1\bigr)=k-f([k\varphi ]+1),\]
由楼上的证明过程不难看出有 $0\leqslant [k\varphi ]+1\leqslant k$ 成立，由此结合式 \eqref{20121019czhjfghds} 即得
\[k-f([k\varphi ]+1)=k-\bigl[([k\varphi ]+1)\varphi \bigr]=k+1-1-\bigl[\bigl([(k+1-1)\varphi ]+1\bigr)\varphi \bigr]=[(k+1)\varphi ],\]
所以
\[f(k+1)=[(k+1)\varphi ],\]
故由第二数学归纳法知 $f(n)=[n\varphi ]$, $n\in \mbb N$。

其实一开始看着 8# 的等式也有点胆怯，没想到细想了下就意外顺利解决了……最近做题运气不错啊

这是我算出来的前9999项

前9999项.zip (33.27 KB)

下载次数: 2

2012-10-20 02:05

程序如下，用C语言写的：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAX_LENGTH 10000
   
5. 
   
6. int f[MAX_LENGTH];
   
7. 
   
8. int main ( void )
   
9. {
   
10.         int i;
    
11.         char file_name[32];
    
12.         FILE * fp;
    
13. 
    
14.         sprintf( file_name, "前%d项.csv", MAX_LENGTH - 1 );
    
15. 
    
16.         fp = (FILE *)fopen( file_name, "w" );
    
17.         if ( fp == NULL )
    
18.                 fp = stdout;
    
19. 
    
20.         f[0] = f[1] = 0;
    
21.         fprintf( fp, "n,f(n)\n", 0, f[0] );
    
22.         fprintf( fp, "%d,%d\n", 0, f[0] );
    
23.         fprintf( fp, "%d,%d\n", 1, f[1] );
    
24.         for ( i = 2 ; i < MAX_LENGTH ; i ++ )
    
25.         {
    
26.                 f[i] = i - 1 - f[f[i - 1]+1];
    
27.                 fprintf( fp, "%d,%d\n", i, f[i] );
    
28.         }
    
29.         fclose( fp );
    
30. 
    
31.         return EXIT_SUCCESS;
    
32. }

复制代码

前99999项

前99999项.zip (330.99 KB)

下载次数: 0

2012-10-20 02:02

其实就是把“#define MAX_LENGTH 10000”改成了“#define MAX_LENGTH 100000”而已，多加了一个“0”而已。

9# kuing


还有个地方没看明白，
为什么$n=\left[ k\varphi  \right]+k+1$时，$\left[ (n-1)\varphi  \right]=k-1$ ，
而$n=\left[ k\varphi  \right]+k+2$时，$\left[ (n-1)\varphi  \right]=k$ ？

9# kuing


还有个地方没看明白，
为什么$n=\left[ k\varphi  \right]+k+1$时，$\left[ (n-1)\varphi  \right]=k-1$ ，
而$n=\left[ k\varphi  \right]+k+2$时，$\left[ (n-1)\varphi  \right]=k$ ？
hongxian 发表于 2012-10-20 12:10

$n=[k\varphi]+k+1$ 是 $[n\varphi]=k$ 的最小的解，所以 $[(n-1)\varphi]$ 就肯定变成 $k-1$ 了。
而当 $[n\varphi]=k$ 有两个解时 $n=[k\varphi]+k+2$ 就是较大的解，所以 $[(n-1)\varphi]$ 仍然是 $k$

10# kuing
K 版威武，这些题看来也很顽固，真是“非暴力不合作”啊

16# 都市侠影

呵呵嗯，除了归纳猜想，暂时想不到别的证法了……