Tên dãy số và số hạng tổng quát của dãy

Nội dung từ topic sumset sang, do thớt du lịch dưới biển lâu quá nên mình vớt một phần nội dung của thớt kia lên bờ.

Đề bài như sau (chép nguyên xi)

Một trong các solution

Gọi T(N) là số cách biểu diễn thoả đề bài.

Đối với trường hợp N chẵn, xét trường hợp N = 6:
6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 4
6 = 2 + 2 + 2
6 = 2 + 4

Giờ chia thành 2 nhóm
Nhóm có số 1 ở vế phải, số lượng là T(5) = 4
6 = 1 + 5 = 1 + (1 + 1 + 1 + 1 + 1)
6 = 1 + 5 = 1 + (1 + 1 + 1 + 2)
6 = 1 + 5 = 1 + (1 + 2 + 2)
6 = 1 + 5 = 1 + (1 + 4)
Nhóm không có số 1 vế phải, số lượng là T(6/2) = T(3) = 2
6 = 2(1 + 1 + 1)
6 = 2(1 + 2)

Vậy T(2n) = T(2n-1) + T(n)

Đối với trường hợp N lẻ, vì N lẻ nên trong biểu diễn phải có 1, suy ra T(2n+1) = T(2n)
7 = 6 + 1 = 1 + (1 + 1 + 1 + 1 + 1 + 1)
7 = 6 + 1 = 1 + (1 + 1 + 1 + 1 + 2)
7 = 6 + 1 = 1 + (1 + 1 + 2 + 2)
7 = 6 + 1 = 1 + (1 + 1 + 4)
7 = 6 + 1 = 1 + (2 + 2 + 2)
7 = 6 + 1 = 1 + (2 + 4)

Hay T(2n) = T(2n-1) + T(n) = T(2n-2) + T(n)

Tóm lại, có công thức truy hồi như sau:

  • T(1) = 1
  • T(2) = 2
  • T(2n) = T(2n-2) + T(n)
  • T(2n+1) = T(2n)

Mình muốn hỏi dãy kết quả của bài trên (sequence) có được đặt tên hay không? Có công thức tổng quát cho dãy?

2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166,...

Vì mình thấy nó có tính chất thế này:

Ban đầu loại đi các phần tử trùng nhau

2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, ...

Trừ 2 phần tử liên tiếp, được dãy mới giống như dãy ban đầu.

2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26,...

Nếu tiếp tục lặp lại, 2 bước, khử phần tử trùng và trừ 2 phần tử liên tiếp, thì được các dãy như sau. Trong đó các dãy được đánh dấu (*) là các dãy giống như dãy kết quả.

2, 4, 6, 10, 14, 20, 26,...
2, 2, 4, 4, 6,... // *
2, 4, 6,...
2, 2,... // *
2,...

Vì dãy là vô tận, nên sau mỗi lần khử và trừ thì được dãy cũ, cứ thế lặp đi lặp lại liên tục.

3 Likes

Vậy ta có dãy u[1] = 2, u[n] = u[n-1] + u[n div 2], có mã số là A000123.

3 Likes

Cũng chục ngày rồi, tick luôn cái solution.
Dù gì phần này cũng thuộc partition problem.

Chắc khái niệm “số cách biểu diễn tổng lũy thừa của 2” là công thức tổng quát rồi, không chuyển sang công thức đại số được nữa.

1 Like

bạn có thể nói lại cái công thức truy hồi cho mik đc không ạ và mik nghĩ không cần xét chẵn lẽ vẫn có công thức tổng quát như của rogp10 ạ

Cái đó cũng là hệ thức truy hồi.

Cho dãy số <u1, u2, u3, u4, … un, …>

Công thức tổng quát un là un = f(n), trong đó f là hàm số chỉ phụ thuộc vào n.

Hệ thức truy hồi, phần un có dạng

  • un = f(un-1), f là hàm số chỉ phụ thuộc vào un-1
  • Hoặc, un = f(u1, u2, …, un-1), f là hàm số, hàm số phụ thuộc tất cả các giá trị đứng trước un trong dãy.

Cả mình và @rog10 đều đưa ở dạng truy hồi, không có tổng quát gì cả.
Với lại mình chưa tìm ra hàm biểu diễn ở mức tổng quát. :kissing:

2 Likes

Cái link bay rồi anh ạ

Đề bài có ở mục này rồi bạn.

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?